Submission #10,440

2024-04-02 14:08:00

cpp17

Accepted 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;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	3ms	1832 KiB
		2	Accepted	3ms	2056 KiB
subtask2	40/40
		3	Accepted	3ms	2260 KiB
		4	Accepted	3ms	2344 KiB
		5	Accepted	4ms	2496 KiB
		6	Accepted	3ms	2932 KiB
		7	Accepted	4ms	3112 KiB
		8	Accepted	4ms	3184 KiB
		9	Accepted	4ms	3436 KiB
subtask3	30/30
		10	Accepted	3ms	3380 KiB
		11	Accepted	19ms	4108 KiB
		12	Accepted	71ms	7868 KiB
		13	Accepted	72ms	10320 KiB
		14	Accepted	133ms	14564 KiB
		15	Accepted	190ms	14052 KiB
		16	Accepted	192ms	13864 KiB
		17	Accepted	185ms	14892 KiB
subtask4	30/30
		18	Accepted	8ms	4956 KiB
		19	Accepted	37ms	15032 KiB
		20	Accepted	65ms	7100 KiB
		21	Accepted	112ms	12692 KiB
		22	Accepted	196ms	15248 KiB
		23	Accepted	180ms	15296 KiB
		24	Accepted	194ms	14676 KiB
		25	Accepted	182ms	14304 KiB
		26	Accepted	192ms	15208 KiB
		27	Accepted	192ms	15204 KiB
		28	Accepted	180ms	15388 KiB