QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#257133#7686. The Phantom Menaceucup-team1321WA 323ms123080kbC++202.6kb2023-11-19 00:26:442023-11-19 00:26:44

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-19 00:26:44]
  • 评测
  • 测评结果：WA
  • 用时：323ms
  • 内存：123080kb
查看
  • [2023-11-19 00:26:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n,m,t,tot;
string a[1000010],b[1000010];
vector<unsigned long long> ha[1000010],hb[1000010];
unsigned long long p[1000010];
int Link[4000010],in[4000010],ou[4000010];
struct dsa
{
	int v,nex,w;
}e[2000010];
vector<int> ans;
unordered_map <unsigned long long,int> mp; 
bool vis[2000010];
void Init()
{
	for (int i=1;i<=n;i++) {
		ha[i].resize(m);
		ha[i][0]=a[i][0]-'a'+1;
	    for (int j=1;j<m;j++) ha[i][j]=ha[i][j-1]*131+a[i][j]-'a'+1;
		hb[i].resize(m);
		hb[i][0]=b[i][0]-'a'+1;
	    for (int j=1;j<m;j++) hb[i][j]=hb[i][j-1]*131+b[i][j]-'a'+1;
	}
	p[0]=1;
	for (int i=1;i<=m;i++) p[i]=p[i-1]*131;
	return ;
}
unsigned long long Hash_A(int i,int l,int r)
{
	if (l>r) return 0;
	unsigned long long val=ha[i][r];
	if (l==0) return val;
	val-=ha[i][l-1]*p[r-l+1];
	return val;
}
unsigned long long Hash_B(int i,int l,int r)
{
	if (l>r) return 0;
	unsigned long long val=hb[i][r];
	if (l==0) return val;
	val-=hb[i][l-1]*p[r-l+1];
	return val;
}
void Insert(int x,int y,int z)
{
	ou[x]++;in[y]++;
	e[++t].nex=Link[x];e[t].v=y;e[t].w=z;Link[x]=t;
	vis[t]=false;
	return;
}
void dfs(int now)
{
	for (int i=Link[now];i;i=e[i].nex) {
		if (vis[e[i].w]) continue;
		vis[e[i].w]=true;
		Link[now]=e[i].nex;
		dfs(e[i].v);
		ans.push_back(e[i].w);
	}
	return ;
}
void Solve()
{
	cin>>n>>m;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) cin>>b[i];
	Init();
	for (int len=0;len<m;len++) {
		mp.clear();
		t=0;
		for (int i=1;i<=tot;i++) Link[i]=0;
		tot=0;
		for (int i=1;i<=n;i++) {
			unsigned long long pre=Hash_A(i,0,len-1),suf=Hash_A(i,len,m-1);
			if (mp.find(pre)==mp.end()) mp[pre]=++tot,ou[tot]=in[tot]=0;
			if (mp.find(suf)==mp.end()) mp[suf]=++tot,ou[tot]=in[tot]=0;
			Insert(mp[pre],mp[suf],i);
		}
		for (int i=1;i<=n;i++) {
			unsigned long long pre=Hash_B(i,0,m-1-len),suf=Hash_B(i,m-len,m-1);
			if (mp.find(pre)==mp.end()) mp[pre]=++tot,ou[tot]=in[tot]=0;
			if (mp.find(suf)==mp.end()) mp[suf]=++tot,ou[tot]=in[tot]=0;
			Insert(mp[pre],mp[suf],i+n);
		}
		bool fla=true;
		for (int i=1;i<=tot;i++)
		  if (in[i]!=ou[i]) {
		  	  fla=false;
		  	  break;
		  }
		if (!fla) continue; 
		ans.clear();
		dfs(1);
		if (ans.size()<2*n) continue;
		for (int i=(int)ans.size()-1;i>=0;i--)
		  if (ans[i]<=n) cout<<ans[i]<<' ';
		cout<<'\n';
		for (int i=(int)ans.size()-1;i>=0;i--)
		  if (ans[i]>n) cout<<ans[i]-n<<' ';
		cout<<'\n';
		return ;
	}
	cout<<-1<<'\n';
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int T;
	cin>>T;
	while (T) {
		Solve();
		T--;
	}
	return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 15ms
memory: 123080kb

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: 323ms
memory: 121332kb

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: 205ms
memory: 122472kb

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: 0
Accepted
time: 211ms
memory: 122360kb

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 
1 2 
-1
-1
2 1 
2 1 
-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 1 
2 1 
-1
-1
2 1 
1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2 1 
2 1 
-1
-1
-1
-1
-1
2 1 
1 2 
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 500000 cases (500000 test cases)

Test #5:

score: 0
Accepted
time: 191ms
memory: 122344kb

input:

333333
1 3
cbb
bfa
1 3
bbb
bfa
1 3
abb
bfa
1 3
fab
bfa
1 3
eab
bfa
1 3
dab
bfa
1 3
cab
bfa
1 3
bab
bfa
1 3
aab
bfa
1 3
ffa
bfa
1 3
efa
bfa
1 3
dfa
bfa
1 3
cfa
bfa
1 3
bfa
bfa
1 3
afa
bfa
1 3
fea
bfa
1 3
eea
bfa
1 3
dea
bfa
1 3
cea
bfa
1 3
bea
bfa
1 3
aea
bfa
1 3
fda
bfa
1 3
eda
bfa
1 3
dda
bfa
1 3
c...

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 333333 cases (333333 test cases)

Test #6:

score: 0
Accepted
time: 163ms
memory: 122384kb

input:

333333
3 1
c
b
b
b
f
a
3 1
b
b
b
b
f
a
3 1
a
b
b
b
f
a
3 1
f
a
b
b
f
a
3 1
e
a
b
b
f
a
3 1
d
a
b
b
f
a
3 1
c
a
b
b
f
a
3 1
b
a
b
b
f
a
3 1
a
a
b
b
f
a
3 1
f
f
a
b
f
a
3 1
e
f
a
b
f
a
3 1
d
f
a
b
f
a
3 1
c
f
a
b
f
a
3 1
b
f
a
b
f
a
3 1
a
f
a
b
f
a
3 1
f
e
a
b
f
a
3 1
e
e
a
b
f
a
3 1
d
e
a
b
f
a
3 1
c...

output:

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

result:

ok 333333 cases (333333 test cases)

Test #7:

score: 0
Accepted
time: 161ms
memory: 122068kb

input:

250000
1 4
hbca
fhaa
1 4
gbca
fhaa
1 4
fbca
fhaa
1 4
ebca
fhaa
1 4
dbca
fhaa
1 4
cbca
fhaa
1 4
bbca
fhaa
1 4
abca
fhaa
1 4
haca
fhaa
1 4
gaca
fhaa
1 4
faca
fhaa
1 4
eaca
fhaa
1 4
daca
fhaa
1 4
caca
fhaa
1 4
baca
fhaa
1 4
aaca
fhaa
1 4
hhba
fhaa
1 4
ghba
fhaa
1 4
fhba
fhaa
1 4
ehba
fhaa
1 4
dhba
fhaa...

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 250000 cases (250000 test cases)

Test #8:

score: 0
Accepted
time: 138ms
memory: 121264kb

input:

250000
4 1
h
b
c
a
f
h
a
a
4 1
g
b
c
a
f
h
a
a
4 1
f
b
c
a
f
h
a
a
4 1
e
b
c
a
f
h
a
a
4 1
d
b
c
a
f
h
a
a
4 1
c
b
c
a
f
h
a
a
4 1
b
b
c
a
f
h
a
a
4 1
a
b
c
a
f
h
a
a
4 1
h
a
c
a
f
h
a
a
4 1
g
a
c
a
f
h
a
a
4 1
f
a
c
a
f
h
a
a
4 1
e
a
c
a
f
h
a
a
4 1
d
a
c
a
f
h
a
a
4 1
c
a
c
a
f
h
a
a
4 1
b
a
c
a
f...

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
4 3 2 1 
4 3 2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 250000 cases (250000 test cases)

Test #9:

score: 0
Accepted
time: 156ms
memory: 122344kb

input:

200000
1 5
jjjjj
baaaa
1 5
ijjjj
baaaa
1 5
hjjjj
baaaa
1 5
gjjjj
baaaa
1 5
fjjjj
baaaa
1 5
ejjjj
baaaa
1 5
djjjj
baaaa
1 5
cjjjj
baaaa
1 5
bjjjj
baaaa
1 5
ajjjj
baaaa
1 5
jijjj
baaaa
1 5
iijjj
baaaa
1 5
hijjj
baaaa
1 5
gijjj
baaaa
1 5
fijjj
baaaa
1 5
eijjj
baaaa
1 5
dijjj
baaaa
1 5
cijjj
baaaa
1 5
b...

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 200000 cases (200000 test cases)

Test #10:

score: 0
Accepted
time: 131ms
memory: 121832kb

input:

200000
5 1
j
j
j
j
j
b
a
a
a
a
5 1
i
j
j
j
j
b
a
a
a
a
5 1
h
j
j
j
j
b
a
a
a
a
5 1
g
j
j
j
j
b
a
a
a
a
5 1
f
j
j
j
j
b
a
a
a
a
5 1
e
j
j
j
j
b
a
a
a
a
5 1
d
j
j
j
j
b
a
a
a
a
5 1
c
j
j
j
j
b
a
a
a
a
5 1
b
j
j
j
j
b
a
a
a
a
5 1
a
j
j
j
j
b
a
a
a
a
5 1
j
i
j
j
j
b
a
a
a
a
5 1
i
i
j
j
j
b
a
a
a
a
5 1
h...

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 200000 cases (200000 test cases)

Test #11:

score: -100
Wrong Answer
time: 151ms
memory: 122092kb

input:

250000
2 2
hb
ca
fh
aa
2 2
gb
ca
fh
aa
2 2
fb
ca
fh
aa
2 2
eb
ca
fh
aa
2 2
db
ca
fh
aa
2 2
cb
ca
fh
aa
2 2
bb
ca
fh
aa
2 2
ab
ca
fh
aa
2 2
ha
ca
fh
aa
2 2
ga
ca
fh
aa
2 2
fa
ca
fh
aa
2 2
ea
ca
fh
aa
2 2
da
ca
fh
aa
2 2
ca
ca
fh
aa
2 2
ba
ca
fh
aa
2 2
aa
ca
fh
aa
2 2
hh
ba
fh
aa
2 2
gh
ba
fh
aa
2 2
f...

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
2 1 
2 1 
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

wrong answer not cyclic isomorphism (test case 16585)
English 繁體中文 简体中文

伺服器時間: 2024-12-02 13:35:31 | 開源專案