Rezultati

Up. imeNalogaJezikRezultatČas oddaje
qubit-2017 Pasavci C++ 0/100Prekoračen čas (TLE) 11. maj '17 @ 19:29

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 3,270 MiB 0,004 s OK
#2 5/5 3,359 MiB 0,004 s OK
#3 5/5 3,512 MiB 0,004 s OK
#4 5/5 3,691 MiB 0,004 s OK
#5 5/5 3,906 MiB 0,010 s OK
#6 5/5 4,797 MiB 0,010 s OK
#7 5/5 4,820 MiB 0,010 s OK
#8 5/5 4,820 MiB 0,010 s OK
#9 6/6 4,820 MiB 0,010 s OK
#10 0/6 5,145 MiB 1,526 s Prekoračen čas
#11 6/6 3,156 MiB 0,004 s OK
#12 6/6 3,188 MiB 0,004 s OK
#13 0/6 2,969 MiB 0,004 s Napaka med izvajanjem / ob izhodu
#14 6/6 3,180 MiB 0,004 s OK
#15 0/6 2,828 MiB 0,004 s Napaka med izvajanjem / ob izhodu
#16 6/6 3,156 MiB 0,004 s OK
#17 6/6 3,172 MiB 0,004 s OK
#18 0/6 5,305 MiB 1,508 s Prekoračen čas

Ocenjevani program (n3.cpp):
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <unordered_map>
#include <tuple>
#include <algorithm>
#include <utility>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

typedef long long ll;

class pasavec{
public:
    deque<char> front;
    deque<char> back;
    ll count;
    void breed(pasavec& he, pasavec& she, string& p, int lenp) {
        front.clear();
        back.clear();
        count = 0;
        for (int i = 0; i < lenp - 1 && i < he.front.size(); i++) {
            front.push_back(he.front[i]);
        }
        for (int i = 0; i < lenp - 1 - he.front.size() && i < she.front.size(); i++) {
            front.push_back(she.front[i]);
        }
        for (int i = 0; i < lenp - 1 && i < she.back.size(); i++) {
            back.push_front(she.back[she.back.size() - 1 - i]);
        }
        for (int i = 0; i < lenp - 1 - she.back.size() && i < he.back.size(); i++) {
            back.push_front(he.back[he.back.size() - 1 - i]);
        }
        count += she.count;
        count += he.count;
        string s = "";
        for (auto x : he.back) s += x;
        for (auto x : she.front) s += x;
        //cout << s << endl;
        for (int i = 0; i < s.size() - lenp + 1; i++) {
            bool match = true;
            for (int j = 0; j < lenp; j++) {
                if (s[i + j] != p[j]) {
                    match = false;
                    break;
                }
            }
            if (match) count++;
        }
    }
};

int main(void) {
    cin.tie(nullptr);
    cin.sync_with_stdio(false);

    string p;
    cin >> p;
    int lenp = p.size();
    string s1, s2;
    cin >> s1 >> s2;
    int m;
    cin >> m;
    vector<pasavec> zveri(m+2);
    for (int i = 0; i < lenp - 1 && i < s1.size(); i++) {
        zveri[0].front.push_back(s1[i]);
        zveri[0].back.push_front(s1[s1.size() - 1 - i]);
    }
    for (int i = 0; i < lenp - 1 && i < s2.size(); i++) {
        zveri[1].front.push_back(s2[i]);
        zveri[1].back.push_front(s2[s2.size() - 1 - i]);
    }
    zveri[0].count = zveri[1].count = 0;
    if (s1.size() > lenp) {
        for (int i = 0; i < s1.size() - lenp + 1; i++) {
            bool match = true;
            for (int j = 0; j < lenp; j++) {
                if (s1[i + j] != p[j]) {
                    match = false;
                    break;
                }
            }
            if (match) zveri[0].count++;
        }
    }
    if (s2.size() > lenp) {
        for (int i = 0; i < s2.size() - lenp + 1; i++) {
            bool match = true;
            for (int j = 0; j < lenp; j++) {
                if (s2[i + j] != p[j]) {
                    match = false;
                    break;
                }
            }
            if (match) zveri[1].count++;
        }
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        zveri[i + 2].breed(zveri[a - 1], zveri[b - 1], p, lenp);
    }
    cout << zveri[m + 1].count << endl;

    return 0;
}