QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#246559 | #7686. The Phantom Menace | fAKeZero# | WA | 18ms | 108092kb | C++17 | 4.2kb | 2023-11-10 22:07:40 | 2023-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: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)