QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53751#2102. Gra w kółkoAppleblue17#WA 2ms3764kbC++143.9kb2022-10-05 21:35:442022-10-05 21:35:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-05 21:35:49]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3764kb
  • [2022-10-05 21:35:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int T,len,n,m;
int a[N],b[N];

struct abc{
	int d,n,l;
	bool col;
};


int pos[N*2],id;
bool col[N*2];

abc f[N*2],g[N];
int solve(abc P[N],int siz){
	for(int i=0;i<siz;i++) f[i+siz]=f[i]=P[i];
	
//	cout<<"sol: \n";
//	for(int i=0;i<siz;i++) cout<<"("<<f[i].col<<")"<<f[i].d<<","<<f[i].n<<","<<f[i].l<<" ";
//	cout<<endl;
	
	int st=-1;
	for(int i=0;i<siz;i++){
		if(f[i].n!=1){
			st=i;
			break;
		}
	}
	if(st==-1) return 0;
	
	id=0;
	for(int i=st;i<st+siz;i++){
		g[++id]=f[i];
		if(id>1 && g[id].n>1 && g[id-1].n==1){
			int r=id,l=id-1;
			while(g[l].n==1) l--;
			if((r-l)%2==0){
				int d_=0,n_=0;
				for(int t=l;t<r;t++) d_+=g[t].d+g[t].l;
				d_+=g[r].d;
				for(int t=l+1;t<=r;t+=2) d_-=g[t].d;
				
				for(int t=l;t<=r;t+=2) n_+=g[t].n;
				
				id=l-1;
				g[++id]=((abc){d_,n_,g[r].l,g[r].col});
			}
			else{
				for(int t=l+1;t<r;t++){
					g[t].d=g[t].n=2;
					if((t-l)%2) g[t].l=0;
				}
			}
		}
	}
	if(g[id].n==1){
		g[++id]=g[1];
		int r=id,l=id-1;
		while(g[l].n==1) l--;
		if((r-l)%2==0){
			int d_=0,n_=0;
			for(int t=l;t<r;t++) d_+=g[t].d+g[t].l;
			d_+=g[r].d;
			for(int t=l+1;t<=r;t+=2) d_-=g[t].d;
			
			for(int t=l;t<=r;t+=2) n_+=g[t].n;
			
			id=l-1;
			g[++id]=((abc){d_,n_,g[r].l,g[r].col});
		}
		else{
			for(int t=l+1;t<r;t++){
				g[t].d=g[t].n=2;
				if((t-l)%2) g[t].l=0;
			}
		}
		if(l>1){
			for(int i=1;i<id;i++) g[i]=g[i+1];
			id--;
		}
	}
	
//	for(int i=1;i<=id;i++) cout<<"("<<g[i].col<<")"<<g[i].d<<","<<g[i].n<<","<<g[i].l<<" ";
//	cout<<endl;
	
	if(id==1) return (g[1].col)?-1:1;
	
	int black_=0,black_2=0,black_1=0,black_pos,white_=0,white_1=0,white_pos;
	for(int i=1;i<=id;i++){
		int lst=(i==1)?(id):(i-1);
		if(g[i].n<3) continue;
		if(g[i].col){
			if(g[i].d>g[i].n) black_++;
			else if(g[lst].l && g[i].l) black_2++;
			else if(g[lst].l || g[i].l) black_1++,black_pos=i;
		}
		else{
			if(g[i].d>g[i].n) white_++;
			else if(g[lst].l || g[i].l) white_1++,white_pos=i;
		}
	}
	if(black_ || black_2 || black_1>=2){
		if(white_ || white_1) return 0;
		else return -1;
	}
	else if(black_1==0){
		if(white_ || white_1) return 1;
		else{
			int s=0;
			for(int i=1;i<=id;i++) s^=g[i].l;
			if(s==0) return -1;
			else return 1;
		}
	}
	else if(black_1==1){
		if(white_ || white_1>=2) return 1;
		int tot=-1;
		abc R[N];
		
		for(int i=1;i<=id;i++) f[i-1]=g[i];
		int pos=black_pos-1,lst=(pos+id-1)%id,nxt=(pos+1)%id;
		if(f[pos].l){
			f[nxt].d+=f[pos].l;
			f[pos].l=0;
		}
		else{
			f[lst].d+=f[lst].l;
			f[lst].l=0;
		}
		for(int i=0;i<id;i++) f[i].col^=1;
		
		if(white_1){
			for(int i=1;i<=id;i++) R[i-1]=g[i];
			pos=white_pos-1,lst=(pos+id-1)%id,nxt=(pos+1)%id;
			if(R[pos].l){
				R[pos].d+=R[pos].l;
				R[pos].l=0;
			}
			else{
				R[pos].d+=R[lst].l;
				R[lst].l=0;
			}
			for(int i=0;i<id;i++) R[i].col^=1;
			return max(-solve(f,id),-solve(R,id));
		}
		else return -solve(f,id);
	}
}

int main(){
//	freopen("1.txt","r",stdin);
	cin>>T;
	while(T--){
		cin>>len>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=m;i++) cin>>b[i];
		if(n+m==len){
			puts("C");
			continue;
		}
		
		id=0;
		int p=1,q=1;
		while(p<=n && q<=m){
			if(a[p]<b[q]) pos[++id]=a[p],col[id]=0,p++;
			else pos[++id]=b[q],col[id]=1,q++;
		}
		while(p<=n) pos[++id]=a[p],col[id]=0,p++;
		while(q<=m) pos[++id]=b[q],col[id]=1,q++;
		
		int st=0;
		for(int i=2;i<=id;i++){
			if(col[i]!=col[i-1]){
				st=i;
				break;
			}
		}
		
		int pid=0;
		for(int i=1;i<=id;i++) pos[i+id]=pos[i]+len,col[i+id]=col[i];
		for(int l=st,r;l<st+id;l=r+1){
			r=l;
			while(col[r+1]==col[l]) r++;
			f[pid++]=(abc){pos[r]-pos[l]+1,r-l+1,pos[r+1]-pos[r]-1,col[l]};
		}
		int ans=solve(f,pid);
		if(ans==1) puts("B");
		else if(ans==-1) puts("C");
		else if(ans==0) puts("R");
		
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3536kb

input:

4
11 3 3
3 8 11
1 6 9
11 4 7
2 7 8 11
1 3 4 5 6 9 10
11 1 5
10
1 3 6 8 11
11 2 4
9 11
1 7 8 10

output:

R
C
C
C

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

4
11 4 2
1 3 5 6
2 4
13 5 5
3 6 7 8 10
1 2 4 9 13
11 5 1
2 5 7 8 11
10
13 6 4
1 2 4 5 6 7
3 8 9 10

output:

B
R
B
B

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 3488kb

input:

4
13 6 3
3 4 5 11 12 13
1 8 9
11 4 2
2 4 5 11
1 3
13 4 5
4 8 11 13
2 3 6 7 9
13 4 4
1 7 9 12
2 5 8 10

output:

B
B
C
C

result:

ok 4 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

4
13 5 4
1 2 9 11 13
3 5 6 10
13 5 4
1 2 7 11 12
3 5 8 13
13 4 5
2 3 6 12
4 5 7 8 13
11 1 5
5
2 3 4 6 7

output:

R
B
C
C

result:

ok 4 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

4
13 3 6
1 2 11
7 8 9 10 12 13
13 5 4
4 5 7 8 12
1 2 11 13
13 4 4
5 7 10 11
1 6 8 13
11 2 4
5 10
1 4 8 11

output:

B
B
B
C

result:

ok 4 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

4
13 5 5
4 8 10 11 12
1 2 3 5 9
11 4 2
1 5 9 10
8 11
13 5 4
1 3 4 6 12
5 9 10 11
13 5 4
1 9 11 12 13
3 4 8 10

output:

B
B
B
R

result:

ok 4 lines

Test #7:

score: 0
Accepted
time: 2ms
memory: 3716kb

input:

4
15 5 5
1 2 6 11 15
3 4 5 10 14
15 5 5
3 4 5 9 15
1 7 11 12 13
15 5 5
1 6 7 8 10
3 4 5 9 15
15 6 1
1 2 4 5 6 15
3

output:

C
R
C
B

result:

ok 4 lines

Test #8:

score: 0
Accepted
time: 2ms
memory: 3624kb

input:

4
15 3 5
7 9 11
6 8 10 12 13
15 5 5
7 10 11 13 14
1 3 5 8 12
15 5 5
1 3 9 14 15
2 4 5 6 10
15 5 5
1 3 6 11 15
2 4 8 10 12

output:

C
R
R
B

result:

ok 4 lines

Test #9:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

4
15 6 4
2 3 6 13 14 15
1 4 7 12
15 4 3
1 5 13 14
3 9 15
15 6 4
2 3 4 6 7 15
1 5 12 13
15 8 7
1 2 4 5 7 9 14 15
3 6 8 10 11 12 13

output:

C
B
B
C

result:

ok 4 lines

Test #10:

score: -100
Wrong Answer
time: 2ms
memory: 3720kb

input:

5
15 4 4
2 5 9 12
4 6 10 14
15 3 6
7 11 14
2 3 4 6 9 12
15 5 5
1 2 6 9 15
5 8 12 13 14
15 5 5
8 9 12 13 15
4 5 6 11 14
15 5 5
1 2 5 6 11
3 7 8 9 12

output:

R
C
R
R
B

result:

wrong answer 3rd lines differ - expected: 'B', found: 'R'