QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53647#2102. Gra w kółkoAppleblue17#WA 0ms7820kbC++144.0kb2022-10-05 16:32:352022-10-05 16:32:37

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 16:32:37]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7820kb
  • [2022-10-05 16:32:35]
  • 提交

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;
	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]=f[st];
		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_+=f[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;
	
	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;
		vector <abc> Q;
		
		for(int i=1;i<=id;i++) Q.push_back(g[i]);
		int pos=black_pos-1,lst=(pos+id-1)%id,nxt=(pos+1)%id;
		if(Q[pos].l){
			Q[nxt].d+=Q[pos].l;
			Q[pos].l=0;
		}
		else{
			Q[lst].d+=Q[lst].l;
			Q[lst].l=0;
		}
		for(int i=0;i<id;i++) Q[i].col^=1;
		tot=max(tot,-solve(Q));
		
		if(white_1){
			Q.clear();
			for(int i=1;i<=id;i++) Q.push_back(g[i]);
			pos=white_pos-1,lst=(pos+id-1)%id,nxt=(pos+1)%id;
			if(Q[pos].l){
				Q[pos].d+=Q[pos].l;
				Q[pos].l=0;
			}
			else{
				Q[pos].d+=Q[lst].l;
				Q[lst].l=0;
			}
			for(int i=0;i<id;i++) Q[i].col^=1;
			tot=max(tot,-solve(Q));
		}
		return tot;
	}
	
}

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");
		
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7724kb

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: 0ms
memory: 7820kb

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'