10440 2024. 04. 02 14:08:00 111 Túlcsordulás cpp17 Elfogadva 100/100 196ms 15388 KiB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define MOD (int)1000000007
#define BASE (int)256

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
	cin>>N;
	string A,B;
	cin>>A>>B;
	for(char&c:B){
		c='0'+'1'-c;
	}
	vector<int>p(N+1,1),ha(N+1),hb(N+1);
	for(int i=0;i<N;i++){
		p[i+1]=p[i]*BASE%MOD;
		ha[i+1]=(ha[i]*BASE+A[i])%MOD;
		hb[i+1]=(hb[i]*BASE+B[i])%MOD;
	}
	int Q;
	cin>>Q;
	while(Q--){
		int x,y,L;
		cin>>x>>y>>L;
		int l=0,h=L;
		while(l<h){
			int m=(l+h)/2;
			if((ha[x+m+1]-ha[x]*p[m+1]+MOD*MOD)%MOD==(hb[y+m+1]-hb[y]*p[m+1]+MOD*MOD)%MOD){
				l=m+1;
			}
			else{
				h=m;
			}
		}
		cout<<(h==L||A[x+h]=='0'?1:0)<<' ';
	}
	cout<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1832 KiB
2 Elfogadva 3ms 2056 KiB
subtask2 40/40
3 Elfogadva 3ms 2260 KiB
4 Elfogadva 3ms 2344 KiB
5 Elfogadva 4ms 2496 KiB
6 Elfogadva 3ms 2932 KiB
7 Elfogadva 4ms 3112 KiB
8 Elfogadva 4ms 3184 KiB
9 Elfogadva 4ms 3436 KiB
subtask3 30/30
10 Elfogadva 3ms 3380 KiB
11 Elfogadva 19ms 4108 KiB
12 Elfogadva 71ms 7868 KiB
13 Elfogadva 72ms 10320 KiB
14 Elfogadva 133ms 14564 KiB
15 Elfogadva 190ms 14052 KiB
16 Elfogadva 192ms 13864 KiB
17 Elfogadva 185ms 14892 KiB
subtask4 30/30
18 Elfogadva 8ms 4956 KiB
19 Elfogadva 37ms 15032 KiB
20 Elfogadva 65ms 7100 KiB
21 Elfogadva 112ms 12692 KiB
22 Elfogadva 196ms 15248 KiB
23 Elfogadva 180ms 15296 KiB
24 Elfogadva 194ms 14676 KiB
25 Elfogadva 182ms 14304 KiB
26 Elfogadva 192ms 15208 KiB
27 Elfogadva 192ms 15204 KiB
28 Elfogadva 180ms 15388 KiB