QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276375#7686. The Phantom MenaceYu_JieWA 450ms382040kbC++142.1kb2023-12-05 20:29:022023-12-05 20:29:03

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-12-05 20:29:03]
  • 评测
  • 测评结果:WA
  • 用时:450ms
  • 内存:382040kb
  • [2023-12-05 20:29:02]
  • 提交

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) {
    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 i=1;i<=4*n;i++) head[i]=deg[i]=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 i=1;i<=idx;i++) if(deg[i]) 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 i=1;i<=top;i++)
            if(stk[i]<=n) ans1.push_back(stk[i]);
            else ans2.push_back(stk[i]-n);
        for(int i:ans1) printf("%d ",i); puts("");
        for(int i:ans2) printf("%d ",i); puts("");
        return ;
    }
    puts("-1");
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 43ms
memory: 379180kb

input:

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

output:

3 2 1 
1 2 3 
-1

result:

ok 2 cases (2 test cases)

Test #2:

score: 0
Accepted
time: 450ms
memory: 382040kb

input:

1000000
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
...

output:

1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
1 
1 
1 
1 
-1
-1
...

result:

ok 1000000 cases (1000000 test cases)

Test #3:

score: 0
Accepted
time: 269ms
memory: 379228kb

input:

500000
1 2
dd
ba
1 2
cd
ba
1 2
bd
ba
1 2
ad
ba
1 2
dc
ba
1 2
cc
ba
1 2
bc
ba
1 2
ac
ba
1 2
db
ba
1 2
cb
ba
1 2
bb
ba
1 2
ab
ba
1 2
da
ba
1 2
ca
ba
1 2
ba
ba
1 2
aa
ba
1 2
dd
aa
1 2
cd
aa
1 2
bd
aa
1 2
ad
aa
1 2
dc
aa
1 2
cc
aa
1 2
bc
aa
1 2
ac
aa
1 2
db
aa
1 2
cb
aa
1 2
bb
aa
1 2
ab
aa
1 2
da
aa
1 2...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 
1 
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 500000 cases (500000 test cases)

Test #4:

score: -100
Wrong Answer
time: 334ms
memory: 379596kb

input:

500000
2 1
d
d
b
a
2 1
c
d
b
a
2 1
b
d
b
a
2 1
a
d
b
a
2 1
d
c
b
a
2 1
c
c
b
a
2 1
b
c
b
a
2 1
a
c
b
a
2 1
d
b
b
a
2 1
c
b
b
a
2 1
b
b
b
a
2 1
a
b
b
a
2 1
d
a
b
a
2 1
c
a
b
a
2 1
b
a
b
a
2 1
a
a
b
a
2 1
d
d
a
a
2 1
c
d
a
a
2 1
b
d
a
a
2 1
a
d
a
a
2 1
d
c
a
a
2 1
c
c
a
a
2 1
b
c
a
a
2 1
a
c
a
a
2 1
d...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 
1 2 
1 2 
2 1 
-1
-1
2 1 
2 1 
1 2 
2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2 1 
2 1 
2 1 
2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 
2 1 
2 1 
2 1 
-1
-1
1 2 
2 1 
1 2 
1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 
2 1 
-1
2 1 
2 1 
-1
-1
-1
-1
-1
...

result:

wrong answer not cyclic isomorphism (test case 11)