QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#426573 | #8679. Tilting Tiles | Fesdrer | WA | 56ms | 12544kb | C++17 | 4.6kb | 2024-05-31 15:23:41 | 2024-05-31 15:23:43 |
Judging History
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'