QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#486427	#385. 游戏	yz_ly	100 ✓	11ms	14336kb	C++14	2.9kb	2024-07-21 19:52:32	2024-07-21 19:52:32

Judging History

This is the latest submission verdict.

[2024-07-21 19:52:32]
Judged

Verdict: 100
Time: 11ms
Memory: 14336kb

Show

[2024-07-21 19:52:32]
Submitted

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void work(int k){
	if(k<0){
		putchar('-');
		k=-k;
	}
	if(k>9)
		work(k/10);
	putchar(k%10+'0');
}
/*
本质是3-SAT,但是发现d很小,所以我们可以枚举这d个x,是A还是B,发现枚举C是不必要的,就不用管
然后每次用2-SAT跑就行了
*/
int n,d,m,id[10],now,cnt,first[100005],val[3][3],dfn[100005],low[100005],co[100005],vis[100005],num,l,ans[100005];
stack<int> g;
char s[50005];
struct node{
	int x,l;
	char y,r;
}b[100005];
struct q1{
	int u,w,nex;
}a[200005];
void add(int u1,int w1){
	a[++cnt]={u1,w1,first[u1]};
	first[u1]=cnt;
}
void Tarjan(int u){
	g.emplace(u);
	vis[u]=1;
	dfn[u]=low[u]=++num;
	for(int i=first[u];i;i=a[i].nex){
		if(!dfn[a[i].w]){
			Tarjan(a[i].w);
			low[u]=min(low[u],low[a[i].w]);
		}
		else if(vis[a[i].w])
			low[u]=min(low[u],dfn[a[i].w]);
	}
	if(dfn[u]==low[u]){
		co[u]=++l;
		vis[u]=0;
		while(g.top()!=u){
			co[g.top()]=l;
			vis[g.top()]=0;
			g.pop();
		}
		g.pop();
	}
}
void solve(int u){
	vis[u]=vis[u>n?u-n:u+n]=1;
	ans[u>n?u-n:u]=u;
	for(int i=first[u];i;i=a[i].nex){
		if(co[u]==co[a[i].w]&&!vis[a[i].w])
			solve(a[i].w);
	}
}
int main(){
	n=read();
	d=read();
	scanf("%s",s+1);
	m=read();
	for(int i=1;i<=m;i++){
		b[i].x=read();
		b[i].y=getchar()-'A';
		b[i].l=read();
		b[i].r=getchar()-'A';
	}
	val[0][2]=val[1][2]=val[2][1]=n;
	for(int i=1;i<=n;i++){
		if(s[i]=='x')
			id[++now]=i;
		s[i]-='a';
	}
	for(int i=0;i<(1<<d);i++){
		for(int j=1;j<=d;j++){
			s[id[j]]=(i>>(j-1))&1;
		}
		cnt=num=l=0;
		for(int j=1;j<=2*n;j++){
			first[j]=dfn[j]=low[j]=0;
		}
		for(int j=1;j<=m;j++){
			if(s[b[j].x]==b[j].y)
				continue;
			if(s[b[j].l]==b[j].r){
				if(s[b[j].x]==0){
					if(b[j].y==1)
						add(b[j].x,b[j].x+n);
					else
						add(b[j].x+n,b[j].x);
				}
				else{
					if(b[j].y==0)
						add(b[j].x,b[j].x+n);
					else
						add(b[j].x+n,b[j].x);
				}
			}
			else{
				add(b[j].x+val[s[b[j].x]][b[j].y],b[j].l+val[s[b[j].l]][b[j].r]);
				add(b[j].l+(val[s[b[j].l]][b[j].r]?0:n),b[j].x+(val[s[b[j].x]][b[j].y]?0:n));
			}
		}
		for(int j=1;j<=2*n;j++){
			if(!dfn[j])
				Tarjan(j);
		}
		int flag=0;
		for(int j=1;j<=n;j++){
			if(co[j]==co[j+n])
				flag=1;
		}
		if(!flag){
			for(int j=1;j<=2*n;j++){
				vis[j]=0;
			}
			for(int j=1;j<=n;j++){
				if(vis[j])
					continue;
				if(co[j]<co[j+n])
					solve(j);
				else
					solve(j+n);
			}
			for(int j=1;j<=n;j++){
				if(s[j]==0)
					putchar(ans[j]>n?'C':'B');
				else if(s[j]==1)
					putchar(ans[j]>n?'C':'A');
				else
					putchar(ans[j]>n?'B':'A');
			}
			return 0;
		}
	}
	work(-1);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 1ms

memory: 7744kb

input:

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

output:

AB

result:

ok

Test #2:

score: 5

Accepted

time: 1ms

memory: 7764kb

input:

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

output:

CA

result:

ok

Test #3:

score: 5

Accepted

time: 1ms

memory: 5708kb

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:

CACAA

result:

ok

Test #4:

score: 5

Accepted

time: 1ms

memory: 5736kb

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:

BABCC

result:

ok

Test #5:

score: 5

Accepted

time: 1ms

memory: 7816kb

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:

CAAACABCBA

result:

ok

Test #6:

score: 5

Accepted

time: 1ms

memory: 5756kb

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:

BAACABBABA

result:

ok

Test #7:

score: 5

Accepted

time: 1ms

memory: 7764kb

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:

BAABABAAAAAAABBABAAA

result:

ok

Test #8:

score: 5

Accepted

time: 1ms

memory: 7856kb

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:

BBBCABAABBBAAACABACC

result:

ok

Test #9:

score: 5

Accepted

time: 1ms

memory: 5808kb

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:

CAABBBACCAAABBBACCBC

result:

ok

Test #10:

score: 5

Accepted

time: 1ms

memory: 8004kb

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:

BCCCCBBBBCAACBBBCBBB

result:

ok

Test #11:

score: 5

Accepted

time: 0ms

memory: 5752kb

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:

ABABBBAAAAABBBBBBABBABABABAABBBBAABBAABBAABBABBBBBABBABABBAAABBABABBAABBAABABBAAAAABBBAAABBAAABBBBBB

result:

ok

Test #12:

score: 5

Accepted

time: 0ms

memory: 7788kb

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:

ABACCACCBCCBAABAAAAABBABBCBAAACCBBBCCACBCCBAABCCCBCCBCBBABCCABBCBCABBCABBCBCABBACCCACBAAACABBBABCCBB

result:

ok

Test #13:

score: 5

Accepted

time: 1ms

memory: 7852kb

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:

AABBACBBAABACBBABBBABAAABAAABBBACBAAABAABBAABABACBBAAAABBBBBBBAAAAABAAABBAAABBAAAABABBBBBABAAABBAABB

result:

ok

Test #14:

score: 5

Accepted

time: 1ms

memory: 7864kb

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:

BBCAABBBCBCBBBBAABBCBBCABCBABCCBAAABCAACBCABABACAAAAAABCACACCCCCCCBBACCBABACBBCBBABBBBCCCBCACCCBABBA

result:

ok

Test #15:

score: 5

Accepted

time: 0ms

memory: 7944kb

input:

5000 0
ccbbbbacccabaacccbccaabcbcbabcabbbcbccacbbcccbccbcacbacaacbccaaacbcaabbacacabaaaccacbaccbbbccaabbbcabcbabaaccbaacacbaaccbacaccababcabbbccacbcabaabababaacccbbababbaabbbaccbabaabbbcbacbbbbbacbbabcabacbbcbaaaaaaccbaaaabccccacaaacabaabaccacabbaacaaccbbcbcaaaccbbccbccbccaacbccacbcbbacaaaaabbacbaab...

output:

-1

result:

ok

Test #16:

score: 5

Accepted

time: 1ms

memory: 8024kb

input:

5000 8
ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

result:

ok

Test #17:

score: 5

Accepted

time: 1ms

memory: 6208kb

input:

5000 8
abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcab...

output:

BCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCA...

result:

ok

Test #18:

score: 5

Accepted

time: 4ms

memory: 14088kb

input:

50000 0
baabcbbaacbbabababbbabcbcbbcabccaaacccbaaabcabccccbbaacbaaacbcacbabbbbabccabaabbcabacacaaabbaccccbcacaaacbcaacbcacbbabbcbabccbbcacbacbbccacbcabcbcbcacbaacaaccbcbabaaacbcbbccbcacacccbbcabcaccacaaaaaacbcaccaacbbbaaaccaaccaaacbacbaaccaabccaababbabaaaaacbaabaccabacbcbabbcbaabacbbacbbaaabababccac...

output:

ABBAAAABBAAABABABAAABAAAAAAABAAABBBAAAABBBAABAAAAAAABBAABBBAAABAABAAAABAAABABBAAABABABABBBAABAAAAAABABBBAAABBAAABAAABAAAABAAAAAABAABAAAAABAAABAAAAAABAABBABBAAAAABABBBAAAAAAAAABABAAAAAABAABAABABBBBBBAAABAABBAAAABBBAABBAABBBAABAABBAABBAAABBABAABABBBBBAABBABAABABAAAABAAAABBABAAABAAABBBABABAAABABBAABAAA...

result:

ok

Test #19:

score: 5

Accepted

time: 11ms

memory: 14336kb

input:

50000 8
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc...

output:

ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

result:

ok

Test #20:

score: 5

Accepted

time: 5ms

memory: 14088kb

input:

50000 8
abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabca...

output:

BCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCA...

result:

ok

Extra Test:

score: 0

Extra Test Passed