QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#53627#2102. Gra w kółkoAppleblue17#WA 3ms7728kbC++143.5kb2022-10-05 15:34:062022-10-05 15:34:07

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 15:34:07]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:7728kb
  • [2022-10-05 15:34:06]
  • 提交

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,col;
};


int pos[N],col[N],id;

abc f[N],g[N];
int solve(vector <abc> P){
	int siz=P.size();
	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,ct=0;
	for(int i=siz-1;i>=0;i--){
		if(f[i].n!=1){
			st=i; ct++;
		}
	}
	if(st==-1) return 0;
	if(ct==1) return (f[st].col==0)?1:-1;
	
	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_+=f[t].d+f[t].l;
				d_+=f[r].d;
				for(int t=l+1;t<=r;t+=2) d_-=f[t].d;
				
				for(int t=l;t<=r;t+=2) n_+=f[t].n;
				
				id=l-1;
				g[++id]=((abc){d_,n_,f[r].l,f[r].col});
			}
			else{
				for(int t=l+1;t<r;t++){
					g[t].d=g[t].n=2;
					if(t%2) g[t].l=0;
				}
			}
		}
	}
//	for(int i=1;i<=id;i++) cout<<"("<<g[i].col<<") "<<g[i].d<<","<<g[i].n<<","<<g[i].l<<" ";
//	cout<<endl;
	
	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>3) 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>3) 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;
		if(white_1==0) return -1;
		vector <abc> L,R;
		for(int i=1;i<=id;i++) L.push_back(g[i]),R.push_back(g[i]);
		
		int pos=black_pos,lst=(pos+id-1)%id,nxt=(pos+1)%id;
		if(L[pos].l){
			L[nxt].d+=L[pos].l;
			L[pos].l=0;
		}
		else{
			L[lst].d+=L[lst].l;
			L[lst].l=0;
		}
		
		pos=white_pos,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++) L[i].col^=1,R[i].col^=1;
		return max(solve(L),solve(R));
	}
	
}

int main(){
	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;
		}
		if(!n){
			puts("C");
			continue;
		}
		if(!m){
			puts("B");
			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;
			}
		}
		
		vector <abc> P;
		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++;
			P.push_back((abc){pos[r]-pos[l]+1,r-l+1,pos[r+1]-pos[r]-1,col[l]});
		}
		
//		for(auto x: P){
//			cout<<x.d<<","<<x.n<<","<<x.l<<" ";
//		}
//		cout<<endl;
		int ans=solve(P);
		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: 3ms
memory: 7716kb

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: -100
Wrong Answer
time: 3ms
memory: 7728kb

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
B
B
B

result:

wrong answer 2nd lines differ - expected: 'R', found: 'B'