QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#426573#8679. Tilting TilesFesdrerWA 56ms12544kbC++174.6kb2024-05-31 15:23:412024-05-31 15:23:43

Judging History

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

  • [2024-05-31 15:23:43]
  • 评测
  • 测评结果:WA
  • 用时:56ms
  • 内存:12544kb
  • [2024-05-31 15:23:41]
  • 提交

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){
	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: 100
Accepted
time: 1ms
memory: 3628kb

input:

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

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

output:

yes

result:

ok single line: 'yes'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

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

g......
.......
hijk...
abcdef.
lmno...

output:

yes

result:

ok single line: 'yes'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

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

.......
..g....
..i.j.k
h.cde.f
ablmn.o

output:

yes

result:

ok single line: 'yes'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

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

......g
.......
...hijk
.abcdef
...lmno

output:

yes

result:

ok single line: 'yes'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

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

......g
.......
...hijk
.abcdfe
...lmno

output:

no

result:

ok single line: 'no'

Test #6:

score: 0
Accepted
time: 0ms
memory: 5688kb

input:

8 10
axudxmgb..
rpyvs.....
fozux.....
xnve......
hx........
t.........
c.........
..........

cxvgxpea..
toyur.....
dnzvx.....
xmuh......
fx........
s.........
b.........
..........

output:

yes

result:

ok single line: 'yes'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

9 7
kbi...b
....mm.
.c.fc..
...j.k.
..f..j.
m....f.
.igl.fl
.g...a.
...f...

k.j....
am.l...
.....ib
..i.m..
..gg.c.
.....ff
.mf....
jf..f.k
cl..b..

output:

no

result:

ok single line: 'no'

Test #8:

score: 0
Accepted
time: 0ms
memory: 5652kb

input:

5 6
iyazl.
bzxf..
yzxe..
czdzzy
j..yk.

jyfziy
azxez.
yzxdl.
bzcz..
ky....

output:

yes

result:

ok single line: 'yes'

Test #9:

score: 0
Accepted
time: 1ms
memory: 5832kb

input:

5 6
iyazly
bzxfz.
yzxek.
czdz..
jy....

kyfzjy
azxez.
yzxdi.
bzcz..
ly....

output:

no

result:

ok single line: 'no'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

3 3
...
.a.
...

...
.a.
...

output:

yes

result:

ok single line: 'yes'

Test #11:

score: 0
Accepted
time: 49ms
memory: 11704kb

input:

500 500
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

no

result:

ok single line: 'no'

Test #12:

score: 0
Accepted
time: 48ms
memory: 12244kb

input:

500 500
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

no

result:

ok single line: 'no'

Test #13:

score: -100
Wrong Answer
time: 56ms
memory: 12544kb

input:

496 495
oanhdonngaokopboqljdalgpfdeqfelhjchogdmrcaqb.ooogggggicgenlbipaprnfbcrapabfjaemrhdelojgbldirmidgihpjfobgopinddhhmacjcqljgajndcgemiepgipqmdgcqndqadkialgjddpkdfhamldedgrejbbgirpmbeqjc.mbipndabllbjbgrlbrhrcaiphrpogicjdcqeqdhdldpefdekqqihifhagjokepbbceqprongafeqmhbripqceodmfaecpgnaenfjjrjbbabaec...

output:

no

result:

wrong answer 1st lines differ - expected: 'yes', found: 'no'