Submission #1156726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156726		alexander707070	Crossing (JOI21_crossing)	C++20	26 / 100	7090 ms	4404 KiB

Main

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

const long long mod[2]={1000000007,1000000009};

long long power[MAXN][2];

struct hesh{
	long long h[2]={0,0};
	int len=0;

	void add(int x){
		h[0]*=4; h[0]+=x+1; h[0]%=mod[0];
		h[1]*=4; h[1]+=x+1; h[1]%=mod[1];
		len++;
	}

	inline friend bool operator == (hesh fr,hesh sc){
		return fr.h[0]==sc.h[0] and fr.h[1]==sc.h[1];
	}

	inline friend hesh operator + (hesh fr,hesh sc){
		return { (fr.h[0]*power[sc.len][0] + sc.h[0])%mod[0] , (fr.h[1]*power[sc.len][1] + sc.h[1])%mod[1] , fr.len+sc.len };
	}
};

int n,l,r,q;
char c;
vector<int> s[4],w;

int val(char c){
	if(c=='J')return 0;
	if(c=='O')return 1;
	if(c=='I')return 2;
}

vector<hesh> vals;

hesh calc(vector<int> s){

	hesh res;
	for(int i=0;i<n;i++)res.add(s[i]);

	return res;
}

void dumb(){
	for(int i=0;i<3;i++){
		for(int f=0;f<3;f++){
			for(int k=0;k<3;k++){

				if(i+f+k==1 or i+f+k==4){
					for(int d=0;d<n;d++)w.push_back((i*s[1][d]+f*s[2][d]+k*s[3][d])%3);
					vals.push_back(calc(w));
					w.clear();
				}

			}
		}
	}
}

void query(){
	hesh curr=calc(w);

	for(auto z:vals){
		if(z==curr){
			cout<<"Yes\n";
			return;
		}
	}

	cout<<"No\n";
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin>>n;
	for(int i=1;i<=3;i++){
		for(int f=1;f<=n;f++){
			cin>>c;
			s[i].push_back(val(c));
		}
	}

	dumb();

	cin>>q;
	for(int i=1;i<=n;i++){
		cin>>c;
		w.push_back(val(c));
	}
	query();

	for(int i=1;i<=q;i++){
		cin>>l>>r>>c;

		for(int f=l-1;f<=r-1;f++)w[f]=val(c);
		query();
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int val(char)':
Main.cpp:36:1: warning: control reaches end of non-void function [-Wreturn-type]
   36 | }
      | ^

• Subtask 1: 3 / 3
• Subtask 2: 0 / 23
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51