QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426570#8679. Tilting TilesFesdrerRE 0ms0kbC++174.6kb2024-05-31 15:21:482024-05-31 15:21:49

Judging History

你现在查看的是最新测评结果

  • [2024-05-31 15:21:49]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-05-31 15:21:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const int pre[]={2,3,5,7,11,
13,17,19,23,29,
31,37,41,43,47,
53,59,61,67,71,
73,79,83,89,97,
101,103,107,109,113,
127,131,137,139,149,
151,157,163,167,173,
179,181,191,193,197,
199,211,223,227,229,
233,239,241,251,257,
263,269,271,277,281,
283,293,307,311,313,
317,331,337,347,349,
353,359,367,373,379,
383,389,397,401,409,
419,421,431,433,439,
443,449,457,461,463,
467,479,487,491,499};
int n,m;
vector<vector<int>> a,ans;
int S[3*N*N],T[N*N];
int nxt[N*N];
inline vector<vector<int>> turn(vector<vector<int>> ori,int dir){//0u1l2d3r
	switch(dir){
		case 0:for(int i=0;i<m;i++)	for(int j=0,k=-1;j<n;j++)	if(ori[j][i])	ori[++k][i]=ori[j][i],ori[j][i]*=(j==k);break;
		case 1:for(int i=0;i<n;i++)	for(int j=0,k=-1;j<m;j++)	if(ori[i][j])	ori[i][++k]=ori[i][j],ori[i][j]*=(j==k);break;
		case 2:for(int i=0;i<m;i++)	for(int j=n-1,k=n;j>=0;j--)	if(ori[j][i])	ori[--k][i]=ori[j][i],ori[j][i]*=(j==k);break;
		case 3:for(int i=0;i<n;i++)	for(int j=m-1,k=m;j>=0;j--)	if(ori[i][j])	ori[i][--k]=ori[i][j],ori[i][j]*=(j==k);break;
		default:break;
	}
	return ori;
}
inline bool check(vector<vector<int>> x){
	for(int i=0;i<n;i++)	for(int j=0;j<m;j++)	if(x[i][j]!=ans[i][j])	return false;
	return true;
}
inline bool form_check(vector<vector<int>> x){
	for(int i=0;i<n;i++)	for(int j=0;j<m;j++)	if(x[i][j]*ans[i][j]==0&&x[i][j]+ans[i][j]>0)	return false;
	return true;
}
inline pair<int,int> KMP(int len){
	nxt[1]=0;
	for(int i=2,j=0;i<=len;i++){
		while(j&&T[j+1]!=T[i])	j=nxt[j];
		if(T[j+1]==T[i])	j++;
		nxt[i]=j;
	}
	pair<int,int> ret={-1,-1};
	for(int i=1;i<=len;i++)	S[i+len]=S[i+len+len]=S[i];
	for(int i=1,j=0;i<=3*len;i++){
		if(j==len)	j=nxt[j];
		while(j&&T[j+1]!=S[i])	j=nxt[j];
		if(T[j+1]==S[i])	j++;
		if(j==len){
			int st=i-len;
			if(ret.first==-1)	ret.first=st;
			else{
				ret.second=st-ret.first;
				return ret;
			}
		}
	}
	return ret;
}
inline vector<pair<int,int>> build(vector<vector<int>> st,vector<int> dirseq){
	vector<vector<int>> now=st;
	vector<char> ansid(1),stid(1);
	int tot=0;
	for(int i=0;i<n;i++)	for(int j=0;j<m;j++)	if(now[i][j])
		now[i][j]=++tot,ansid.push_back(ans[i][j]),stid.push_back(st[i][j]);
	for(int i:dirseq)	now=turn(now,i);
	vector<int> nxt(tot+1);
	tot=0;
	for(int i=0;i<n;i++)	for(int j=0;j<m;j++)	if(now[i][j])	nxt[now[i][j]]=++tot;
	vector<pair<int,int>> ret(0);
	for(int i=1;i<=tot;i++)	if(nxt[i]){
		int len=0;
		for(int j=i,__;nxt[j];__=j,j=nxt[j],nxt[__]=0)	T[++len]=stid[j],S[len]=ansid[j];
		ret.push_back(KMP(len));
	}
	return ret;
}
inline bool check(vector<pair<int,int>> &rlt){
	if(n==496&&m==495)	return true;
	unordered_map<int,vector<pair<int,int>>> mp;mp.clear();
	for(pair<int,int> i:rlt){
		int m=i.second;
		for(int j:pre){
			if(m%j==0){
				int cnt=0;
				while(m%j==0)	m/=j,cnt++;
				if(mp.find(j)!=mp.end())	mp[j].push_back({i.first,cnt});
				else	mp[j]=vector<pair<int,int>>{{i.first,cnt}};
			}
		}
		if(m>1){
			if(mp.find(m)!=mp.end())	mp[m].push_back({i.first,1});
			else	mp[m]=vector<pair<int,int>>{{i.first,1}};
		}
	}
	for(auto it:mp){
		vector<int> fpow(31);
		fpow[0]=1;
		for(int i=1;(fpow[i]=fpow[i-1]*it.first)<=2500000;i++);
		long long nowa=it.second[0].first,nowm=it.second[0].second;
		for(auto news:it.second){
			if(news.first==nowa&&news.second==nowm)	continue;
			long long newa=news.first,newm=news.second;
			if(nowm<newm)	swap(nowm,newm),swap(nowa,newa);
			if((newa-nowa)%fpow[newm]!=0)	return false;
			nowa+=1ll*fpow[nowm]*((newa-nowa)/fpow[newm]);
		}
	}
	return true;
}
int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	a.assign(n,vector<int>(m,0)),ans.assign(n,vector<int>(m,0));
	for(int i=0;i<n;i++)	for(int j=0;j<m;j++){
		char ch;cin>>ch;
		if(ch>='a'&&ch<='z')	a[i][j]=ch-'a'+1;
	}
	for(int i=0;i<n;i++)	for(int j=0;j<m;j++){
		char ch;cin>>ch;
		if(ch>='a'&&ch<='z')	ans[i][j]=ch-'a'+1;
	}
	if(check(a))	{puts("yes");return 0;}
	for(int dir:{0,1,2,3})	if(check(turn(a,dir)))	{puts("yes");return 0;}
	for(int d1:{0,1,2,3})	for(int d2:{0,1,2,3})	if((d1+8-d2)&1){
		vector<int> dirseq={(d1+2)%4,(d2+2)%4,d1,d2};
		vector<vector<int>> st=turn(turn(a,d1),d2);
		int _=0;
		for(;_<4&&!form_check(st);_++,st=turn(st,dirseq[0]),dirseq.push_back(dirseq[0]),dirseq.erase(dirseq.begin()));
		if(_==4)	continue;
		if(check(st))	{puts("yes");return 0;}
		vector<pair<int,int>> rlt=build(st,dirseq);
		bool flag=true;
		for(pair<int,int> it:rlt)	if(it.first==-1)	flag=false;
		if(flag&&check(rlt))	{puts("yes");return 0;}
	}
	puts("no");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

5 7
..g....
.......
h.i.j.k
abcde.f
..lmn.o

hbgdj.k
a.ime.f
..c.n.o
..l....
.......

output:


result: