QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422552#8679. Tilting TilesEric_caiWA 27ms16348kbC++145.0kb2024-05-27 16:01:502024-05-27 16:01:50

Judging History

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

  • [2024-05-27 16:01:50]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:16348kb
  • [2024-05-27 16:01:50]
  • 提交

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'