QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#244737	#7686. The Phantom Menace	rascalrabbit	WA	461ms	366096kb	C++14	2.5kb	2023-11-09 15:11:18	2023-11-09 15:11:19

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-09 15:33:42]
hack成功，自动添加数据
(//qoj.ac/hack/445)

[2023-11-09 15:11:19]
评测

测评结果：WA
用时：461ms
内存：366096kb

查看

[2023-11-09 15:11:18]
提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define ALL(tar) tar.begin(), tar.end()
#define forn(name, b, n) for (int name = (b); name <= (int)(n); name++)
#define competition cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pair<int, ii> > EdgeList;
const ll INF = 0x3f3f3f3f;
const ll MS = 2e6+10;
ll MOD=1e18+3,base=1331,pw[MS];
int n,m;
vector<ll> sufa[MS],sufb[MS],prea[MS],preb[MS],dfn;
string sa[MS],sb[MS];
ll mul(ll a,ll b){
	return (__int128)a*b%MOD;
}
ll add(ll a,ll b){
	return (a+b)%MOD;
}
ll sub(ll a,ll b){
	return (a+MOD-b)%MOD;
}
void getpre(string & str,vector<ll> &ha){
	ha.resize(m+2);
	ha[0]=0;
	forn(i,1,m){
		ha[i]=add(mul(ha[i-1],base),str[i-1]);
	}
}
void getsuf(string & str,vector<ll> &ha){
	ha.resize(m+2);
	ha[m+1]=0;
	for(int i=m;i>=1;--i){
		ha[i]=add(ha[i+1],mul(str[i-1],pw[m-i]));
	}
}
int fa[MS],de[MS],now,ecnt,vis[MS];
map<ll,int> na;
int getid(ll h){
	if(!na.count(h)){
		na[h]=++now;
		fa[now]=now;
	}
	return na[h];
}
vii g[MS];
int findf(int u){
	return u==fa[u]?u:fa[u]=findf(fa[u]);
}
void add(int u,int v){
	++ecnt;
	fa[findf(u)]=findf(v);
	de[u]^=1,de[v]^=1;
	g[u].pb({v,ecnt});
	g[v].pb({u,ecnt});
}
void dfs(int u){
	for(auto [v,id]:g[u]){
		if(vis[id])continue;
		dfn.pb(id);
		vis[id]=1;
		dfs(v);
	}
}
void solve()
{
	cin>>n>>m;
	pw[0]=1;
	forn(i,1,m)pw[i]=mul(pw[i-1],base);
	forn(i,1,n)cin>>sa[i],getpre(sa[i],prea[i]),getsuf(sa[i],sufa[i]);
	forn(i,1,n)cin>>sb[i],getpre(sb[i],preb[i]),getsuf(sb[i],sufb[i]);
	forn(len,0,m-1){
			vi a,b;
		forn(i,1,now)g[i].clear(),de[i]=0;
		now=0;
		na.clear();
	
		forn(i,1,ecnt)vis[i]=0;
		ecnt=0;
		dfn.clear();
		forn(i,1,n){
			ll hl=prea[i][len],hr=sufa[i][len+1];
			int u=getid(hl),v=getid(hr);
			add(u,v);
		}
		forn(i,1,n){
			ll hl=preb[i][m-len],hr=sufb[i][m-len+1];
			int u=getid(hl),v=getid(hr);
			add(u,v);
		}
		assert(ecnt==2*n);
		int ok=1;
		forn(i,1,now)if(findf(1)!=findf(i))ok=0;
		forn(i,1,now)if(de[i]){
			ok=0;
		}
		if(!ok)continue;
		dfs(1);
	
		for(auto v:dfn)if(v<=n)a.pb(v);
		else b.pb(v);
		for(auto v:a)printf("%d ",v);puts("");
		for(auto v:b)printf("%d ",v-n);puts("");
		return;
	}
	puts("-1");
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	while(t--)
		solve();
}
/*
1
1 2
cd
fa
*/

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 43ms

memory: 366096kb

input:

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

output:

1 3 2 
1 2 3 
-1

result:

ok 2 cases (2 test cases)

Test #2:

score: 0

Accepted

time: 461ms

memory: 365224kb

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:

result:

ok 1000000 cases (1000000 test cases)

Test #3:

score: 0

Accepted

time: 283ms

memory: 363408kb

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: 324ms

memory: 365000kb

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:

result:

wrong answer not cyclic isomorphism (test case 17)