QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#246559#7686. The Phantom MenacefAKeZero#WA 18ms108092kbC++174.2kb2023-11-10 22:07:402023-11-10 22:07:41

Judging History

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

  • [2024-10-08 14:11:03]
  • hack成功,自动添加数据
  • (/hack/941)
  • [2024-10-08 10:05:28]
  • hack成功,自动添加数据
  • (/hack/940)
  • [2024-10-07 19:51:15]
  • hack成功,自动添加数据
  • (/hack/938)
  • [2024-10-07 19:28:01]
  • hack成功,自动添加数据
  • (/hack/937)
  • [2024-10-07 17:16:32]
  • hack成功,自动添加数据
  • (/hack/936)
  • [2024-10-07 16:53:09]
  • hack成功,自动添加数据
  • (/hack/935)
  • [2024-10-07 16:22:17]
  • hack成功,自动添加数据
  • (/hack/934)
  • [2023-11-10 22:07:41]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:108092kb
  • [2023-11-10 22:07:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int T,n,m;
char ch[1000100];
vector<char> s1[1000010],s2[1000010];
const int mod1=998244353,mod2=1e9+7;
const int o1=133331,o2=37;
struct hs {
    int hs1,hs2;
    bool operator < (const hs &a) const {
        if(hs1!=a.hs1) return hs1<a.hs1;
        return hs2<a.hs2;
    }
};
vector<hs> hs1[1001000],hs2[1000100];
map<hs,int> M1,M2;
int tot,pw1[1000100],pw2[1000100];
hs get1(int id, int l,int r) {
    hs o; 
    o.hs1 = (hs1[id][r].hs1-1ll*hs1[id][l-1].hs1*pw1[r-l+1]%mod1+mod1)%mod1; 
    o.hs2 = (hs1[id][r].hs2-1ll*hs1[id][l-1].hs2*pw2[r-l+1]%mod2+mod2)%mod2;
    return o;
}
hs get2(int id, int l,int r) {
    hs o;
    o.hs1=(hs2[id][r].hs1-1ll*hs2[id][l-1].hs1*pw1[r-l+1]%mod1+mod1)%mod1;
    o.hs2=(hs2[id][r].hs2-1ll*hs2[id][l-1].hs2*pw2[r-l+1]%mod2+mod2)%mod2;
    return o;
}
void pre() {
    pw1[0]=1; int N=1e6; pw2[0]=1;
    for(int i=1;i<=N;i++) pw1[i]=1ll*pw1[i-1]*o1%mod1,pw2[i]=1ll*pw2[i-1]*o2%mod2;
}
struct xx{
    int next,to;
    int id,tp;
}way[4000010];
int head[2000010],num;
void add(int from,int to,int id,int tp) {
    way[++num].next=head[from];
    way[num].to=to; way[num].id=id; way[num].tp=tp;
    head[from]=num;
}
vector<pair<int,int> > ans;
void dfs(int x){
    vector<pair<int,int> > res;
    for(int &i=head[x];i;){
        int ii=i;
        i=way[i].next;
        dfs(way[ii].to);
        res.emplace_back(way[ii].id,way[ii].tp);
    }
    reverse(res.begin(),res.end());
    for(auto x:res) ans.push_back(x);
}
int main() {
    scanf("%d",&T);
    pre();
    while(T--) {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)  {
            scanf("%s",ch);
            for(int j=0;j<m;++j) s1[i].push_back(ch[j]);
        }
        for(int i=1;i<=n;i++) {
            scanf("%s",ch);
            for(int j=0;j<m;++j) s2[i].push_back(ch[j]);
        }
        for(int i=1;i<=n;i++) {
            int h1=0; int h2=0;
            hs o; o.hs1=0; o.hs2=0;
            hs1[i].push_back(o);
            for(int j=0;j<m;++j) {
                h1=(1ll*h1*o1%mod1+s1[i][j])%mod1;
                h2=(1ll*h2*o2%mod2+s1[i][j])%mod2;
                hs r; r.hs1=h1; r.hs2=h2;
                hs1[i].push_back(r);
            }
        }
        for(int i=1;i<=n;i++) {
            int h1=0; int h2=0;
            hs o; o.hs1=0; o.hs2=0;
            hs2[i].push_back(o);
            for(int j=0;j<m;++j) {
                h1=(1ll*h1*o1%mod1+s2[i][j])%mod1;
                h2=(1ll*h2*o2%mod2+s2[i][j])%mod2;
                hs r; r.hs1=h1; r.hs2=h2;
                hs2[i].push_back(r);
            }
        }
        bool ok=0;
        for(int j=1;j<=m;++j) {
            for(int i=1;i<=tot;i++) head[i]=0; 
            M1.clear(); tot=0; M2.clear(); num=0;
            for(int i=1;i<=n;i++) {
                hs o1=get1(i,1,j);
                hs o2=get1(i,j+1,m);
                if(!M1[o1]) {
                    M1[o1]=++tot;
                }
                if(!M2[o2]) {
                    M2[o2]=++tot;
                }
                add(M1[o1],M2[o2],i,0);
            }   
            bool flag=1;
            for(int i=1;i<=n;i++) {
                hs o1=get2(i,1,m-j);
                hs o2=get2(i,m-j+1,m);
                if(!M2[o1]) {
                    flag=0;
                    break;
                }
                if(!M1[o2]) {
                    flag=0;
                    break;
                }
                add(M2[o1],M1[o2],i,1);
            }
            if(!flag)  continue;        
            ans.clear();
            dfs(1);
            if(ans.size()==2*n) {
                ok=1;
                break;
            }
        }
        if(!ok) {
            printf("-1\n");
        } else {
            for(auto u:ans) {
                if(u.second==0) printf("%d ",u.first);
                
            }puts("");
            for(auto u:ans) {
                if(u.second==1) printf("%d ",u.first);
                
            }puts("");
        }
        for(int i=1;i<=n;i++) {
            hs1[i].clear(); hs2[i].clear();
            s1[i].clear();
            s2[i].clear();
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 18ms
memory: 108092kb

input:

2
3 3
abc
ghi
def
bcd
efg
hia
1 3
abc
def

output:

2 3 1 
3 2 1 
-1

result:

wrong answer not cyclic isomorphism (test case 1)