QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422552 | #8679. Tilting Tiles | Eric_cai | WA | 27ms | 16348kb | C++14 | 5.0kb | 2024-05-27 16:01:50 | 2024-05-27 16:01:50 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
const int base=131;
char c[505*505];
int n,m,a[505][505],b[505][505],len,d[505][505],cnt,tmp[505][505];
char s[505][505],t[505][505];
void ch(int k)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) b[i][j]=0;
if(k==0)
{
for(int i=1;i<=n;i++)
{
len=0;
for(int j=1;j<=m;j++)
if(a[i][j]!=0) b[i][++len]=a[i][j];
}
}
if(k==1)
{
for(int i=1;i<=n;i++)
{
len=m;
for(int j=m;j>=0;j--)
if(a[i][j]!=0) b[i][len--]=a[i][j];
}
}
if(k==2)
{
for(int j=1;j<=m;j++)
{
len=0;
for(int i=1;i<=n;i++)
if(a[i][j]!=0) b[++len][j]=a[i][j];
}
}
if(k==3)
{
for(int j=1;j<=m;j++)
{
len=n;
for(int i=n;i>=1;i--)
if(a[i][j]!=0) b[len--][j]=a[i][j];
}
}
}
int cir[10][8]={{},{1,2,0,3},{1,3,0,2},{0,2,1,3},{0,3,1,2},{2,1,3,0},{2,0,3,1},{3,1,2,0},{3,0,2,1}};
bool check()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(c[a[i][j]]!=t[i][j]) return 0;
return 1;
}
bool fl,ff;
int vis[505*505],to[505*505],sz;
ll hh[2*505*505],p[2*505*505],w;
char str[2*505*505],chr[2*505*505];
int res[505*505],tp[505][505];
ll get_hh(int l,int r)
{
return ((hh[r]-hh[l-1]*p[r-l+1])%mod+mod)%mod;
}
int main()
{
freopen("1.in","r",stdin);
int now,r,md,lst,pr;
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
c[0]='.';
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>s[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>t[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]!='.')
{
d[i][j]=++cnt;
c[cnt]=s[i][j];
}
for(int i=1;i<=8;i++)
{
memcpy(a,d,sizeof(a));
for(int j=4;j<8;j++) cir[i][j]=cir[i][j-4];
for(int j=0;j<=3;j++)
{
fl|=check(),ff=1;
memcpy(tmp,a,sizeof(tmp));
for(int k=j;k<j+4;k++)
{
ch(cir[i][k]);
memcpy(a,b,sizeof(a));
}
memcpy(tp,a,sizeof(tp));
for(int k=j;k<j+4;k++)
{
ch(cir[i][k]);
memcpy(a,b,sizeof(a));
}
memcpy(a,tp,sizeof(a));
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
if((a[x][y]==0 && t[x][y]!='.') || (a[x][y]!=0 && t[x][y]=='.')) ff=0;
if(ff==1)
{
/*cout<<i<<' '<<j<<endl;
for(int x=1;x<=n;x++)
{
for(int y=1;y<=m;y++)
cout<<c[a[x][y]];
cout<<'\n';
}*/
for(int x=0;x<=n*m;x++) res[x]=-1;
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
if(a[x][y]!=0) to[a[x][y]]=b[x][y],chr[a[x][y]]=t[x][y];
for(int x=1;x<=cnt;x++) vis[x]=0;
w=hh[0]=0,p[0]=1,sz=0;
for(int x=1;x<=cnt;x++)
{
if(vis[x]==1) continue;
now=x;
while(vis[now]==0)
{
vis[now]=1,sz++;
hh[sz]=(hh[sz-1]*base+c[now])%mod,w=(w*base+chr[now])%mod;
p[sz]=p[sz-1]*base%mod,str[sz]=c[now];
now=to[now];
}
for(int pos=sz+1;pos<=sz*2;pos++)
{
hh[pos]=(hh[pos-1]*base+str[pos-sz])%mod;
p[pos]=p[pos-1]*base%mod;
}
md=sz,r=sz,lst=0;
for(int pos=1;pos<=sz;pos++)
{
if(get_hh(pos,pos+sz-1)==w)
{
if(lst!=0) md=pos-lst;
r=pos-1,lst=pos;
}
}
if(r==sz) ff=0;
for(int pm=2;pm<=md;pm++)
{
if(md%pm!=0) continue;
pr=1;
while(md%pm==0)
{
pr*=pm;
md/=pm;
}
if(res[pr]!=-1 && res[pr]!=r%pr) ff=0;
res[pr]=r%pr;
}
}
fl|=ff;
}
memcpy(a,tmp,sizeof(a));
ch(cir[i][j]);
memcpy(a,b,sizeof(a));
}
}
if(fl==1) cout<<"yes\n";
else cout<<"no\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 27ms
memory: 14236kb
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: 13ms
memory: 13088kb
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: 26ms
memory: 14244kb
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: 12ms
memory: 13204kb
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: -100
Wrong Answer
time: 27ms
memory: 16348kb
input:
5 7 ..g.... ....... h.i.j.k abcde.f ..lmn.o ......g ....... ...hijk .abcdfe ...lmno
output:
yes
result:
wrong answer 1st lines differ - expected: 'no', found: 'yes'