QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#935 | #276379 | #7686. The Phantom Menace | N_z_ | Yu_Jie | Success! | 2024-10-07 16:22:16 | 2024-10-07 16:52:35 |
详细
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)
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#276379 | #7686. The Phantom Menace | Yu_Jie | WA | 472ms | 710152kb | C++14 | 2.1kb | 2023-12-05 20:35:25 | 2024-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;
}