Submission #466031

#	Time	Username	Problem	Language	Result	Execution time	Memory
466031		mariowong	Crossing (JOI21_crossing)	C++14	0 / 100	158 ms	11132 KiB

Main

#include <bits/stdc++.h>
#define hmod 1223334444555553LL
using namespace std;

int sz,n,nowl,nowr,l[200005],r[200005],q,blk;
long long val,sum[505],ttl,b[200005],sumb[505],indx[200005],all[505],nowindx;
char c[10]={'a','J','O','I'},ch;
string s,str;
vector <string> v;
map <string,bool> a; 
map <long long,bool> hashing;
void makestring(){
	for (int i=0;i<v.size();i++){
		for (int j=i+1;j<v.size();j++){
			str.clear();
			for (int k=0;k<n;k++){
				if (v[i][k] != v[j][k]){
					for (int l=1;l<=3;l++){
						if (c[l] != v[i][k] && c[l] != v[j][k])
						str+=c[l];
					}
				}
				else
				str+=v[i][k];
			}
			if (!a[str]){
				v.push_back(str);
				a[str]=true;
			}
		}
	}
	for (int i=0;i<v.size();i++){
		val=0;
		for (int j=0;j<n;j++){
			for (long long k=1;k<=3;k++){
				if (v[i][j] == c[k])
				val+=k*b[j];
			}		
			val%=hmod;
		}
	//	cerr << v[i] << "\n";
		hashing[val]=true;
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i=1;i<=3;i++){
		cin >> s;
		a[s]=true; v.push_back(s);
	}
	b[0]=1;
	for (int i=1;i<n;i++){
		b[i]=b[i-1]*4;
		b[i]%=hmod;
	}
	makestring();
	sz=int(sqrt(n)); 
	if (sz*sz != n) blk=sz+1;
	else blk=sz;
	nowl=0; nowr=sz-1;
	for (int i=1;i<=blk;i++){
		l[i]=nowl; r[i]=nowr;
		nowl=nowr+1; nowr=min(n-1,nowl+sz-1);
	}
	cin >> q >> str;
	for (int i=0;i<n;i++){
		for (int j=1;j<=3;j++){
			if (str[i] == c[j])
			indx[i]=j;
		}
	}
	for (int i=1;i<=blk;i++){
		for (int j=l[i];j<=r[i];j++){
			sum[i]+=indx[j]*b[j]; sum[i]%=hmod;
			sumb[i]+=b[j]; sumb[i]%=hmod;
		}
		ttl+=sum[i]; ttl%=hmod;
		all[i]=-1;
	}
//	cerr << ttl << "\n";
	if (hashing[ttl]) cout << "Yes\n";
	else cout << "No\n";
	for (int i=1;i<=q;i++){
		cin >> nowl >> nowr >> ch;
 		nowl--; nowr--;
		ttl=0;
		for (int j=1;j<=3;j++){
			if (ch == c[j]) nowindx=j;
		}
		for (int j=1;j<=blk;j++){
			if (nowl > r[j] || nowr < l[j])
			continue;
			if (nowl <= l[j] && r[j] <= nowr){
				all[j]=nowindx;
				sum[j]=nowindx*sumb[j];
			}
			else
			if (l[j] <= nowl && nowl <= r[j]){
				if (all[j] == -1){
					for (int k=nowl;k<=min(nowl,r[j]);k++){
						sum[j]-=b[k]*indx[k]; sum[j]+=b[k]*nowindx;
						indx[k]=nowindx;
					}
				}
				else
				{
					for (int k=l[j];k<nowl;k++){
						indx[k]=all[j];
					}
					for (int k=nowl;k<=min(nowr,r[j]);k++){
						sum[j]-=b[k]*all[j]; sum[j]+=b[k]*nowindx;
						indx[k]=nowindx;
					}
					for (int k=min(nowr,r[j])+1;k<=r[j];k++){
						indx[k]=all[j];
					}
				}
				all[j]=-1;
			}
			else
			if (l[j] <= nowr && nowr <= r[j]){
				if (all[j] == -1){
					for (int k=max(nowl,l[j]);k<=nowr;k++){
						sum[j]-=b[k]*indx[k]; sum[j]+=b[k]*nowindx;
						indx[k]=nowindx;
					}
				}
				else
				{
					for (int k=l[j];k<max(nowl,l[j]);k++){
						indx[k]=all[j];
					}
					for (int k=max(nowl,l[j]);k<=nowr;k++){
						sum[j]-=b[k]*all[j]; sum[j]+=b[k]*nowindx;
						indx[k]=nowindx;
					}
					for (int k=nowr+1;k<=r[j];k++){
						indx[k]=all[j];
					}
				}
				all[j]=-1;
			}
			while (sum[j] < 0) sum[j]+=hmod;
		}
		for (int j=1;j<=blk;j++){
			ttl+=sum[j]; ttl%=hmod;
		}
	//	cerr << ttl << "\n";
		if (hashing[ttl]) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void makestring()':
Main.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i=0;i<v.size();i++){
      |               ~^~~~~~~~~
Main.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for (int j=i+1;j<v.size();j++){
      |                  ~^~~~~~~~~
Main.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i=0;i<v.size();i++){
      |               ~^~~~~~~~~

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