10929 2024. 04. 19 20:17:25 zsombor Túlcsordulás cpp17 Elfogadva 100/100 171ms 17728 KiB 
#include <iostream>
#include <vector>
using namespace std;
using ull = unsigned long long;

int n, q, x, y, l;
string a, b;
vector <ull> pwr(4e5, 1);
vector <ull> h(4e5, 0);

ull hsh(int L, int R) {
    L--;
    ull ret = h[R];
    if (L > -1) ret -= h[L] * pwr[R - L];
    return ret;
}

bool check(int M) {
    return hsh(x, x + M - 1) == hsh(y, y + M - 1);
}

void solve() {
    cin >> x >> y >> l;
    y += n;
    int L = 0, R = l + 1, M;
    while (R - L > 1) {
        M = (L + R) / 2;
        check(M) ? L = M : R = M;
    }
    cout << (R > l || a[x + R - 1] == '0' ? "1 " : "0 ");
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> a >> b >> q;
    for (char c : b) a.push_back('1' - (c - '0'));

    for (int i = 1; i < 2 * n; i++) pwr[i] = pwr[i - 1] * 3;
    h[0] = a[0] - '0' + 1;
    for (int i = 1; i < 2 * n; i++) h[i] = h[i - 1] * 3 + (a[i] - '0' + 1);

    while (q--) solve();
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 7ms 14212 KiB
2 Elfogadva 7ms 14404 KiB
subtask2 40/40
3 Elfogadva 7ms 14620 KiB
4 Elfogadva 7ms 14836 KiB
5 Elfogadva 8ms 15044 KiB
6 Elfogadva 7ms 15384 KiB
7 Elfogadva 7ms 15332 KiB
8 Elfogadva 8ms 15412 KiB
9 Elfogadva 8ms 15336 KiB
subtask3 30/30
10 Elfogadva 7ms 15340 KiB
11 Elfogadva 20ms 15488 KiB
12 Elfogadva 63ms 16444 KiB
13 Elfogadva 64ms 16704 KiB
14 Elfogadva 118ms 17280 KiB
15 Elfogadva 162ms 17256 KiB
16 Elfogadva 159ms 17252 KiB
17 Elfogadva 163ms 17456 KiB
subtask4 30/30
18 Elfogadva 12ms 15764 KiB
19 Elfogadva 34ms 17488 KiB
20 Elfogadva 57ms 16512 KiB
21 Elfogadva 97ms 17404 KiB
22 Elfogadva 171ms 17588 KiB
23 Elfogadva 156ms 17592 KiB
24 Elfogadva 162ms 17560 KiB
25 Elfogadva 159ms 17564 KiB
26 Elfogadva 167ms 17588 KiB
27 Elfogadva 163ms 17588 KiB
28 Elfogadva 158ms 17728 KiB