Rezultati

Up. imeNalogaJezikRezultatČas oddaje
zerodays-2017 Pasavci C++ 0/100Napaka med izvajanjem / ob izhodu (RTE) 11. maj '17 @ 20:28

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 3,141 MiB 0,004 s OK
#2 5/5 3,234 MiB 0,004 s OK
#3 5/5 3,246 MiB 0,004 s OK
#4 5/5 3,168 MiB 0,004 s OK
#5 5/5 3,172 MiB 0,004 s OK
#6 5/5 3,215 MiB 0,004 s OK
#7 0/5 3,211 MiB 0,004 s Napačen odgovor
Tvoj izhod:
​1548
<<<EOF>>>
Pravilen izhod:
​1602
<<<EOF>>>
#8 5/5 3,297 MiB 0,004 s OK
#9 6/6 3,215 MiB 0,004 s OK
#10 0/6 3,234 MiB 1,521 s Prekoračen čas
#11 6/6 3,211 MiB 0,004 s OK
#12 6/6 3,129 MiB 0,004 s OK
#13 0/6 3,195 MiB 0,004 s Klicana nedovoljena funkcija
Stderr:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::substr: __pos (which is 18446744073709551609) > this->size() (which is 8)
#14 6/6 3,207 MiB 0,004 s OK
#15 0/6 3,105 MiB 0,004 s Klicana nedovoljena funkcija
Stderr:
terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::substr: __pos (which is 18446744073709551609) > this->size() (which is 2)
#16 6/6 3,211 MiB 0,004 s OK
#17 6/6 3,121 MiB 0,004 s OK
#18 6/6 3,215 MiB 0,004 s OK

Ocenjevani program (pasavci.cpp):
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <tuple>

using namespace std;

struct par {
    int a, b;
};

struct neki {
    int a;
    string l, d;
};

int n, ps;
string p;

vector<par> pasavci;
vector<int> memo; 
vector<string> str_memo_l;
vector<string> str_memo_d;

int ponov(const string& a) {
    int c = 0;
    for (int i = 0; i < max(static_cast<int>(a.size()) - ps + 1, 0); ++i) {
        if (a.substr(i, ps) == p) {
            c++;
        }
    }
    return c;
}

neki count(int a, int b, int k) {
    string levo, desno;
    int v = 0;
    
    if (memo[a] != -1) {
        levo = str_memo_l[a];
        v += memo[a];
        v %= 1000000007;
    } else {
        neki N = count(pasavci[a].a, pasavci[a].b, a);
        levo = N.d;
        v += N.a;
        v %= 1000000007;
    }

    if (memo[b] != -1) {
        desno = str_memo_d[b];
        v += memo[b];
        v %= 1000000007;
    } else {
        neki N = count(pasavci[b].a, pasavci[b].b, b);
        desno = N.l;
        v += N.a;
        v %= 1000000007;
    }
    
    neki N;
    
    v += ponov(levo + desno);
    v %= 1000000007;

//     if (levo.size() < ps) {
//         levo += desno.substr(0, min(static_cast<int>(desno.size()), ps - static_cast<int>(levo.size())));
//     } if (desno.size() < ps) {
//         desno = levo.substr(min(static_cast<int>(levo.size()) - (static_cast<int>(desno.size()) - ps), 0)) + desno;
//     }
    
    int PS = ps-1;
    
    str_memo_l[k] = str_memo_l[a] + desno;
    str_memo_d[k] = levo + str_memo_d[b];
    
    str_memo_l[k] = str_memo_l[k].substr(0, ps-1);
    str_memo_d[k] = str_memo_d[k].substr(static_cast<int>(str_memo_d[k].size()) - (ps-1));
    
    N.l = str_memo_l[k];
    N.d = str_memo_d[k];
    
    N.a = v;
    
        return N;
}

int main() {
    string a, b;
    cin >> p;
    ps = p.size();
    cin >> a >> b;
    
    cin >> n;
    
    memo = vector<int>(n + 3, -1);
    str_memo_l = vector<string>(n + 3);
    str_memo_d = vector<string>(n + 3);

    memo[0] = ponov(a);
    memo[1] = ponov(b);
    
    str_memo_l[0] = a.substr(max(static_cast<int>(a.size()) - ps - 1, 0));
    str_memo_d[0] = a.substr(0, min(ps, static_cast<int>(a.size())));
    
    str_memo_l[1] = b.substr(max(static_cast<int>(b.size()) - ps - 1, 0));
    str_memo_d[1] = b.substr(0, min(ps, static_cast<int>(b.size())));
    
    pasavci.push_back({0, 0});
    pasavci.push_back({0, 0});
        
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        pasavci.push_back({a, b});
    }
        
    par zadn = pasavci[pasavci.size() - 1];
    cout << count(zadn.a, zadn.b, pasavci.size()-1).a << endl;
    return 0;
}