QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276375 | #7686. The Phantom Menace | Yu_Jie | WA | 450ms | 382040kb | C++14 | 2.1kb | 2023-12-05 20:29:02 | 2023-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: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)