QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#873822	#385. 游戏	lizhixuan	10	43ms	27416kb	C++17	4.9kb	2025-01-26 23:53:52	2025-01-26 23:54:03

Judging History

你现在查看的是最新测评结果

[2025-01-26 23:54:03]
评测

测评结果：10
用时：43ms
内存：27416kb

查看

[2025-01-26 23:53:52]
提交

answer

#include <bits/stdc++.h>
using namespace std;
struct node{
	int a,b;
	char c,d;
}q[100005];
char s[100005],t[100005];
vector<int> edges[100005],ddges[100005],ot,scc,v[50005];
vector<vector<int>> sccs;
bool b[100005],ok[100005],okk[100005],okkk[50005];
int c[10];
int n,d,m;
inline void dfs(int x){
	b[x]=true;
	for(auto y:edges[x]){
		if(!b[y]){
			dfs(y);
		}
	}
	ot.push_back(x);
}
inline void dfs2(int x){
	b[x]=true;
	for(auto y:ddges[x]){
		if(!b[y]){
			dfs2(y);
		}
	}
	scc.push_back(x);
}
inline void ae(int x,int y){
	edges[x].push_back(y);
	ddges[y].push_back(x);
}
inline void solve(){
	sccs.clear();
	for(int i=1;i<=2*n;i++){
		ok[i]=b[i]=false;
		edges[i].clear();
		ddges[i].clear();
	}
	for(int i=1;i<=m;i++){
		int a=q[i].a,b=q[i].b;
		char c=q[i].c,d=q[i].d;
		if(okk[a]&&okk[b]){
			if(c=='C'&&d!='C'){
				return;
			}
		} else if(okk[a]){
			if(c=='C'){
				if(s[b]=='x'||s[b]=='c'){
					if(d=='A'){
						ae(b+n,b);
					} else if(d=='B'){
						ae(b,b+n);
					} else{
						return;
					}
				} else if(s[b]=='a'){
					if(d=='B'){
						ae(b+n,b);
					} else{
						ae(b,b+n);
					}
				} else{
					if(d=='A'){
						ae(b+n,b);
					} else{
						ae(b,b+n);
					}
				}
			}
		} else if(okk[b]){
			if(d!='C'){
				if(s[a]=='x'||s[a]=='c'){
					if(c=='A'){
						ae(b,b+n);
					} else{
						ae(b+n,b);
					}
				} else if(s[b]=='a'){
					if(c=='B'){
						ae(b,b+n);
					} else{
						ae(b+n,b);
					}
				} else{
					if(c=='A'){
						ae(b,b+n);
					} else{
						ae(b+n,b);
					}
				}
			}
		} else{
			if(s[a]=='x'&&s[b]=='x'){
				if(c!='C'&&d=='C'){
					if(c=='A'){
						ae(b+n,b);
					} else{
						ae(b,b+n);
					}
				}
			} else if(s[a]=='x'){
				if(c!='C'){
					int x=a,y=b;
					if(c=='B'){
						x+=n;
					}
					if(s[b]=='a'){
						if(d=='C')
							y+=n;
					} else if(s[b]=='b'){
						if(d=='C')
							y+=n;
					} else{
						if(d=='B')
							y+=n;
					}
					int nx=x,ny=y;
					if(nx<=n)
						nx+=n;
					else
						nx-=n;
					if(ny<=n)
						ny+=n;
					else
						ny-=n;
					ae(x,y);
					ae(ny,nx);
				}
			} else if(s[b]=='x'){
				if(d!='C'){
					int x=a,y=b;
					if(s[a]=='a'){
						if(c=='C')
							x+=n;
					} else if(s[a]=='b'){
						if(c=='C')
							x+=n;
					} else{
						if(c=='B')
							x+=n;
					}
					if(d=='B'){
						y+=n;
					}
					int nx=x,ny=y;
					if(nx<=n)
						nx+=n;
					else
						nx-=n;
					if(ny<=n)
						ny+=n;
					else
						ny-=n;
					ae(x,y);
					ae(ny,nx);
				} else{
					int x=a;
					if(s[a]=='a'){
						if(c=='C')
							x+=n;
					} else if(s[a]=='b'){
						if(c=='C')
							x+=n;
					} else{
						if(c=='B')
							x+=n;
					}
					int nx=x;
					if(nx<=n)
						nx+=n;
					else
						nx-=n;
					ae(x,nx);
				}
			} else{
				int x=a,y=b;
				if(s[a]=='a'){
					if(c=='C')
						x+=n;
				} else if(s[a]=='b'){
					if(c=='C')
						x+=n;
				} else{
					if(c=='B')
						x+=n;
				}
				if(s[b]=='a'){
					if(d=='C')
						y+=n;
				} else if(s[b]=='b'){
					if(d=='C')
						y+=n;
				} else{
					if(d=='B')
						y+=n;
				}
				int nx=x,ny=y;
				if(nx<=n)
					nx+=n;
				else
					nx-=n;
				if(ny<=n)
					ny+=n;
				else
					ny-=n;
				ae(x,y);
				ae(ny,nx);
			}
		}
	}
	ot.clear();
	for(int i=1;i<=2*n;i++){
		if(!b[i]&&!okk[i]){
			dfs(i);
		}
	}
	reverse(ot.begin(),ot.end());
	for(int i=1;i<=2*n;i++){
		b[i]=false;
	}
	for(auto i:ot){
		if(!b[i]&&!okk[i]){
			scc.clear();
			dfs2(i);
			for(auto i:scc){
				if(i>n){
					i-=n;
				}
				if(ok[i]){
					return;
				}
				ok[i]=true;
			}
			for(auto i:scc){
				if(i>n){
					i-=n;
				}
				ok[i]=false;
			}
			sccs.push_back(scc);
		}
	}
	reverse(sccs.begin(),sccs.end());
	for(auto i:sccs){
		for(auto j:i){
			int jj=j;
			if(jj>n)
				jj-=n;
			if(!okkk[jj]){
				okkk[jj]=true;
				if(!okk[jj]){
					if(j<=n){
						if(s[jj]=='x'||s[jj]=='c'||s[jj]=='b'){
							printf("A");
						} else{
							printf("B");
						}
					} else{
						if(s[jj]=='x'||s[jj]=='c'){
							printf("B");
						} else{
							printf("C");
						}
					}
				} else{
					printf("C");
				}
			}
		}
	}
	throw(1);
}
int main(){
	cin>>n>>d>>s+1>>m;
	for(int i=1;i<=m;i++){
		scanf("%d %c%d %c",&q[i].a,&q[i].c,&q[i].b,&q[i].d);
		if(q[i].a!=q[i].b||q[i].c!=q[i].d){
			v[q[i].a].push_back(i);
			v[q[i].b].push_back(i);
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='x'){
			c[++tot]=i;
		}
	}
	for(int i=0;i<(1<<d);i++){
		try{
			for(int j=1;j<=n;j++){
				okk[j]=false;
			}
			for(int j=1;j<=d;j++){
				if(i>>j-1&1){
					okk[c[j]]=true;
				}
			}
			for(int j=1;j<=n;j++){
				okk[j+n]=okk[j];
			}
			solve();
		} catch(int x){
			return 0;
		}
	}
	cout<<-1;
	
	return 0;
}

源文件, 语言: C++17

詳細信息

Pretests

Final Tests

Test #1:

score: 0

Wrong Answer

time: 1ms

memory: 10692kb

input:

2 0
ba
4
2 C 2 C
1 B 1 A
2 C 1 C
2 B 1 A

output:

BA

result:

wrong answer

Test #2:

score: 0

Wrong Answer

time: 0ms

memory: 11160kb

input:

2 1
xc
4
2 B 2 A
2 A 1 C
2 C 2 C
2 B 1 A

output:

result:

wrong answer

Test #3:

score: 0

Wrong Answer

time: 0ms

memory: 10208kb

input:

5 0
bcbbb
10
1 B 1 C
3 C 1 C
2 B 5 A
1 C 1 C
2 A 5 A
3 A 1 C
2 B 1 C
3 A 1 B
1 B 4 B
1 B 4 A

output:

CCAAA

result:

wrong answer

Test #4:

score: 0

Wrong Answer

time: 2ms

memory: 9928kb

input:

5 2
acxax
10
2 B 1 A
3 C 4 C
4 B 3 C
5 B 3 B
2 B 3 A
3 A 2 A
5 B 1 C
3 B 1 B
2 C 4 C
4 B 2 A

output:

ABCAA

result:

wrong answer

Test #5:

score: 0

Wrong Answer

time: 0ms

memory: 11084kb

input:

10 0
abbbacabab
20
5 A 3 B
9 A 4 C
4 C 10 A
8 B 3 C
6 C 10 A
5 A 9 C
8 A 2 C
5 A 8 B
10 A 10 A
5 B 4 B
6 C 10 C
2 C 4 B
5 C 7 B
5 A 10 B
3 A 7 B
6 B 4 B
3 C 8 B
1 B 3 B
4 B 3 C
8 A 2 A

output:

-1

result:

wrong answer

Test #6:

score: 0

Wrong Answer

time: 1ms

memory: 10692kb

input:

10 4
xbbxccxbxc
20
2 A 10 A
10 C 4 C
1 A 5 A
2 A 2 A
9 C 2 B
2 B 6 C
2 B 9 A
3 B 2 B
4 B 9 A
4 A 5 A
2 B 10 A
3 B 6 A
8 C 8 B
3 B 3 B
3 B 7 A
9 C 6 C
6 A 8 C
4 A 10 A
2 C 4 B
9 C 7 B

output:

AACBCBBAAA

result:

wrong answer

Test #7:

score: 0

Wrong Answer

time: 0ms

memory: 10440kb

input:

20 0
cccccccccccccccccccc
40
15 A 13 C
6 B 19 A
3 C 5 B
20 C 6 C
1 C 10 B
10 C 7 C
13 B 17 A
1 A 3 A
15 A 15 A
13 B 18 B
14 A 4 A
1 A 3 A
4 C 14 A
1 B 6 B
2 B 8 B
3 C 15 A
1 B 17 B
6 A 17 A
12 B 6 A
8 B 1 C
15 B 1 B
18 C 3 C
2 A 8 A
14 B 6 B
15 C 9 A
17 A 10 C
15 A 7 A
8 C 6 A
18 B 12 C
14 C 10 A
9 ...

output:

-1

result:

wrong answer

Test #8:

score: 0

Wrong Answer

time: 1ms

memory: 9800kb

input:

20 0
caaabacbacabbcacabaa
40
7 B 19 C
15 A 12 B
2 A 12 C
20 B 1 B
4 B 4 A
4 A 18 C
4 A 3 A
15 C 12 A
2 C 12 C
15 B 6 A
10 A 12 B
13 C 7 C
2 C 6 C
16 C 18 A
12 B 17 B
8 C 11 B
14 B 11 A
8 B 8 C
19 A 7 C
6 C 3 C
1 C 4 B
1 C 5 A
13 B 4 C
14 B 9 A
11 A 9 C
8 B 16 B
2 C 20 A
2 A 14 C
10 B 13 A
17 A 19 B
...

output:

-1

result:

wrong answer

Test #9:

score: 0

Wrong Answer

time: 2ms

memory: 10140kb

input:

20 8
xccccccxxcxcccccxxxx
40
12 A 18 C
16 C 14 C
10 B 2 C
1 A 10 A
11 A 13 B
15 A 6 B
8 A 14 B
16 A 15 B
4 C 5 C
19 C 4 B
17 C 11 A
12 B 14 C
18 B 17 B
14 A 11 C
16 C 6 C
13 C 20 B
16 B 13 C
8 B 7 C
9 B 16 B
1 B 18 A
7 B 6 A
8 B 19 A
16 C 17 A
8 A 6 A
10 A 14 B
20 C 6 B
13 C 5 A
14 A 3 C
20 B 14 C
4...

output:

BAAABBAAABBAAABBBB

result:

wrong answer

Test #10:

score: 0

Wrong Answer

time: 0ms

memory: 9756kb

input:

20 8
cbabxccxxxxxbaxxaaac
40
8 C 7 C
19 C 12 C
19 A 6 B
6 C 20 B
12 B 18 B
6 A 10 B
11 B 14 B
20 C 18 B
4 A 7 C
18 A 1 A
18 C 14 A
5 B 13 B
3 B 7 A
8 C 1 C
14 B 4 C
13 A 1 A
7 A 19 A
11 B 16 A
9 A 7 A
11 C 4 B
10 B 1 A
1 A 1 B
5 A 8 C
20 C 13 A
3 B 11 B
18 C 13 A
11 A 20 B
3 A 16 C
17 A 5 C
6 C 17 B...

output:

-1

result:

wrong answer

Test #11:

score: 0

Wrong Answer

time: 0ms

memory: 10700kb

input:

100 0
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
200
62 A 60 B
22 A 46 A
87 A 67 B
29 A 43 A
64 B 28 B
83 B 16 A
50 A 64 B
48 A 95 A
28 B 90 A
5 A 12 A
23 B 86 A
62 A 81 B
64 B 9 B
5 A 10 B
89 B 18 B
69 B 62 A
63 A 55 A
28 B 92 B
49 A 43 A
71...

output:

BAABBBBBBBABAABAABBBABBAABABAAAABBAABBABBBBABABAABAABABBABABBBBBABBAAAABBBBBBBABBBBABAAAABBAAABABBAA

result:

wrong answer

Test #12:

score: 0

Wrong Answer

time: 2ms

memory: 10436kb

input:

100 0
cabaabbaaabacbaccbccacbcaaccccbbcccbabbaaaacccbaaabbcaaabaabcaabcbbcaabaabaaccacbaabbacbbacaaabcbbca
200
94 C 31 A
29 B 48 B
89 C 52 A
49 B 11 C
10 C 66 C
90 B 49 B
80 B 19 B
26 B 54 B
20 B 65 B
52 A 80 B
51 A 33 A
94 C 6 C
18 C 60 A
87 B 45 B
12 C 7 A
26 B 57 A
89 C 54 B
4 B 29 B
39 A 67 C
22...

output:

CBCCBBBCBCABAACBBBBCAABABBCCCCBBAABBBABCBCAAABACCCABACCAACCABBACCBABABABCABCBCCBCABACABCCABBBCCCCAAB

result:

wrong answer

Test #13:

score: 0

Wrong Answer

time: 0ms

memory: 9956kb

input:

100 8
cccccxccccccxccccxccccccxcccccccxccccxccccccccccxccccccccccccccccccccccccccccccccccccccxcccccccccccc
200
38 A 13 B
60 A 18 B
36 B 76 B
95 A 7 B
25 A 58 B
53 A 27 A
21 A 78 A
15 A 48 A
52 B 59 A
65 B 68 A
72 A 47 A
95 A 48 A
96 A 67 A
96 A 47 A
46 B 96 A
79 B 36 B
60 A 90 B
5 B 95 A
17 A 99 A
2...

output:

ABBAAAABAABBAAABBBAABABBBBAAAABBBBABBAAABABBBBABBBABAAABAABBABBAABAAAABBBBABAAAAAABBBBABAAAABAAAAAAA

result:

wrong answer

Test #14:

score: 0

Wrong Answer

time: 1ms

memory: 11212kb

input:

100 8
ccbbcaacxxbcxacbcaabxaaccbxcaabacbccaccacbcacxcacccccccbcacbaabbabaacbbababaxabcccacaxabaaacabbcbccc
200
41 A 8 A
75 C 86 C
93 B 26 A
83 C 55 A
49 B 69 B
50 B 54 B
41 A 85 C
43 B 4 A
75 C 95 A
2 A 54 B
14 C 3 A
18 C 79 A
5 B 8 A
61 C 90 B
48 C 96 B
84 A 40 C
55 A 58 B
77 A 47 A
36 A 60 A
2 A 8...

output:

CABCCABCCACABCBABACACAAABAACBABCCCCBCBCABABAACCCABBBCBCBBAACBCBCCBCBBAAAAABACABCBBBBBAACBCBCBABBAABA

result:

wrong answer

Test #15:

score: 5

Accepted

time: 4ms

memory: 11212kb

input:

5000 0
ccbbbbacccabaacccbccaabcbcbabcabbbcbccacbbcccbccbcacbacaacbccaaacbcaabbacacabaaaccacbaccbbbccaabbbcabcbabaaccbaacacbaaccbacaccababcabbbccacbcabaabababaacccbbababbaabbbaccbabaabbbcbacbbbbbacbbabcabacbbcbaaaaaaccbaaaabccccacaaacabaabaccacabbaacaaccbbcbcaaaccbbccbccbccaacbccacbcbbacaaaaabbacbaab...

output:

-1

result:

ok

Test #16:

score: 0

Wrong Answer

time: 4ms

memory: 11284kb

input:

5000 8
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

ABABABABABABBABAABBABABABAABBABABAABBABABABAABBAABBABAABABBABAABABBAABABBAABBAABABABBABABAABBAABABABBAABBAABBAABABABABABABABBABAABBABABAABBABABAABBABABABAABBABABAABBABABAABABABBABABAABABBAABBAABBABAABABABABABABBABABABABAABABABBABABABAABABBAABBAABBAABBABABAABABABBAABBABABAABBABABAABABBABAABABABBABABA...

result:

wrong answer

Test #17:

score: 0

Wrong Answer

time: 4ms

memory: 11848kb

input:

5000 8
abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcab...

output:

BCABCACABBCAACBACBBACACBBCABCAABCABCBCABCAACBBACABCCABABCBCAABCBACBCAACBABCBACBCABACBCAABCBCAABCCABBCABCAACBACBBCABCABCAABCABCCABBCABACCABBCABCABCABCACABABCBCACABCABACBBACBCABACABCABCBCABACACBACBABCABCACBACBACBBCABCABCABCABACACBBCABACCABBCAACBBCABCABCABCAABCABCCABCABBCABCAACBABCBCABCABCABCABCABACCAB...

result:

wrong answer

Test #18:

score: 5

Accepted

time: 21ms

memory: 26904kb

input:

50000 0
baabcbbaacbbabababbbabcbcbbcabccaaacccbaaabcabccccbbaacbaaacbcacbabbbbabccabaabbcabacacaaabbaccccbcacaaacbcaacbcacbbabbcbabccbbcacbacbbccacbcabcbcbcacbaacaaccbcbabaaacbcbbccbcacacccbbcabcaccacaaaaaacbcaccaacbbbaaaccaaccaaacbacbaaccaabccaababbabaaaaacbaabaccabacbcbabbcbaabacbbacbbaaabababccac...

output:

ABBAAAABBAAABABABAAABAAAAAAABAAABBBAAAABBBAABAAAAAAABBAABBBAAABAABAAAABAAABABBAAABABABABBBAABAAAAAABABBBAAABBAAABAAABAAAABAAAAAABAABAAAAABAAABAAAAAABAABBABBAAAAABABBBAAAAAAAAABABAAAAAABAABAABABBBBBBAAABAABBAAAABBBAABBAABBBAABAABBAABBAAABBABAABABBBBBAABBABAABABAAAABAAAABBABAAABAAABBBABABAAABABBAABAAA...

result:

ok

Test #19:

score: 0

Wrong Answer

time: 32ms

memory: 27416kb

input:

50000 8
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

BABAABABABBABAABBABABAABBAABBABAABBAABABABBAABBAABBAABABBAABABABBAABBAABBABAABBABABABAABBAABABABABABBAABABABBAABBABABABAABBABABABAABABABBABAABBABABABAABABBAABBABAABBAABBAABABBAABABBAABABBAABBAABABABABBAABBAABBAABABBABAABBABAABBAABBABAABABBABABAABBABAABBABAABBABAABBAABBABAABABABBABAABBAABBAABBAABBABA...

result:

wrong answer

Test #20:

score: 0

Wrong Answer

time: 43ms

memory: 27088kb

input:

50000 8
abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabca...

output:

ACBACBACBBACABCABCBACCABABCABCBACBACABCBCABACABCCABCABCABCABACBCABCABBCABCABACCABBCACABBCACABBCABCABACBCABCABCABCABACBCABACCABACBCABBCABACACBACBBACBACABCABCCABBACCABBCABACACBBACCABBACACBABCABCACBBACABCBCAACBBACBCAACBBCABACBCAACBACBBACABCCABBACCABCABCABACBBCABCAACBBCAABCBCABCABACCABBACACBACBBCAACBABC...

result:

wrong answer