QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#935#276379#7686. The Phantom MenaceN_z_Yu_JieSuccess!2024-10-07 16:22:162024-10-07 16:52:35

Details

Extra Test:

Wrong Answer
time: 47ms
memory: 392400kb

input:

1
1 50
aaoagphfanslbaaaaaaaaaaaaaaaaaaaaaaaaaaaahaaaapapz
zpapaaaahaaaaaaaaaaaaaaaaaaaaaaaaaaaablsnafhpgaoaa

output:

1 
1 

result:

wrong answer not cyclic isomorphism (test case 1)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276379#7686. The Phantom MenaceYu_JieWA 472ms710152kbC++142.1kb2023-12-05 20:35:252024-10-13 19:46:22

answer

#include<bits/stdc++.h>
typedef unsigned long long ull;
using namespace std;
const int N=4000005,B=131;
int n,m,idx,deg[N],stk[N],top;
int head[N],nxt[N],ver[N],edge[N],tot;
char s[N];
vector<ull> pre1[N],suf1[N],pre2[N],suf2[N];
unordered_map<ull,int> mp;
int get(ull x) {
    if(!mp.count(x)) mp[x]=++idx;
    return mp[x];
}
void add(int x,int y,int z) {
    deg[x]++; deg[y]--;
    nxt[++tot]=head[x]; head[x]=tot; ver[tot]=y; edge[tot]=z;
}
void dfs(int x) {
    for(int i=head[x];i;i=head[x]) {
        head[x]=nxt[i];
        dfs(ver[i]);
        stk[++top]=edge[i];
    }
}
void solve() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);
        pre1[i].clear(); pre1[i].resize(m+2); suf1[i].clear(); suf1[i].resize(m+2);
        for(int j=1;j<=m;j++) pre1[i][j]=pre1[i][j-1]*B+(s[j]-'a'+1);
        ull pw=1; for(int j=m;j>=1;j--,pw*=B) suf1[i][j]=suf1[i][j+1]+(s[j]-'a'+1)*pw;
    }
    for(int i=1;i<=n;i++) {
        scanf("%s",s+1);
        pre2[i].clear(); pre2[i].resize(m+2); suf2[i].clear(); suf2[i].resize(m+2);
        for(int j=1;j<=m;j++) pre2[i][j]=pre2[i][j-1]*B+(s[j]-'a'+1);
        ull pw=1; for(int j=m;j>=1;j--,pw*=B) suf2[i][j]=suf2[i][j+1]+(s[j]-'a'+1)*pw;
    }
    for(int i=1;i<=m;i++) {
        mp.clear(); idx=tot=0;
        for(int j=1;j<=4*n;j++) head[j]=deg[j]=0;
        for(int j=1;j<=n;j++) {
            add(get(pre1[j][i]),get(suf1[j][i+1]^19260817),j);
            add(get(pre2[j][m-i]^19260817),get(suf2[j][m-i+1]),j+n);
        }
        int fl=1;
        for(int j=1;j<=idx;j++) if(deg[j]) fl=0;
        if(!fl) continue;
        top=0; dfs(1);
        if(top!=2*n) continue;
        reverse(stk+1,stk+top+1);
        vector<int> ans1,ans2;
        for(int j=1;j<=top;j++)
            if(stk[j]<=n) ans1.push_back(stk[j]);
            else ans2.push_back(stk[j]-n);
        for(int j:ans1) printf("%d ",j); puts("");
        for(int j:ans2) printf("%d ",j); puts("");
        return ;
    }
    puts("-1");
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}