QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#53717#2102. Gra w kółkoAppleblue17#ML 35ms10744kbC++144.0kb2022-10-05 21:02:232022-10-05 21:02:25

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:02:25]
  • 评测
  • 测评结果:ML
  • 用时:35ms
  • 内存:10744kb
  • [2022-10-05 21:02:23]
  • 提交

answer

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

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


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

abc f[N],g[N];
int solve(int dep,vector <abc> P){
	int siz=P.size();
	for(int i=0;i<siz;i++) f[i+siz]=f[i]=P[i];
	
	if(n==499984) cout<<dep<<" "<<siz<<endl;
//	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;
		vector <abc> L,R;
		
		for(int i=1;i<=id;i++) L.push_back(g[i]);
		int pos=black_pos-1,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;
		}
		for(int i=0;i<id;i++) L[i].col^=1;
		
		if(white_1){
			for(int i=1;i<=id;i++) R.push_back(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(dep+1,L),-solve(dep+1,R));
		}
		else return -solve(dep+1,L);
	}
}

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;
		}
		
		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++;
		
		if(n==499984) puts("ABC");
		
		int st=0;
		for(int i=2;i<=id;i++){
			if(col[i]!=col[i-1]){
				st=i;
				break;
			}
		}
		
		if(n==499984) puts("ABC");
		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]});
		}
		
		if(n==499984) puts("ABC");
		int ans=solve(1,P);
		if(ans==1) puts("B");
		else if(ans==-1) puts("C");
		else if(ans==0) puts("R");
		
	}
}

詳細信息

Test #1:

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

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: 3ms
memory: 3744kb

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: 3ms
memory: 3640kb

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: 3520kb

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: 3ms
memory: 3672kb

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: 1ms
memory: 3696kb

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: 3ms
memory: 3672kb

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

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: 3ms
memory: 3560kb

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: 0
Accepted
time: 0ms
memory: 3636kb

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

result:

ok 5 lines

Test #11:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

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

output:

C
R
B
C
B

result:

ok 5 lines

Test #12:

score: 0
Accepted
time: 4ms
memory: 3584kb

input:

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

output:

B
B
C
B
C

result:

ok 5 lines

Test #13:

score: 0
Accepted
time: 4ms
memory: 3632kb

input:

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

output:

R
B
B
C
B

result:

ok 5 lines

Test #14:

score: 0
Accepted
time: 4ms
memory: 3504kb

input:

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

output:

C
B
C
R
B

result:

ok 5 lines

Test #15:

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

input:

5
100 15 15
3 6 9 29 33 38 41 44 48 57 66 75 82 93 98
4 8 23 31 35 39 43 46 53 62 73 78 87 96 100
100 17 13
1 15 36 46 51 62 63 64 65 67 69 71 72 73 74 76 90
6 31 43 48 49 50 57 66 68 70 75 89 95
100 16 14
1 3 74 76 78 80 82 83 85 87 89 91 93 95 97 99
2 75 77 79 81 84 86 88 90 92 94 96 98 100
100 19...

output:

R
B
B
R
B

result:

ok 5 lines

Test #16:

score: 0
Accepted
time: 3ms
memory: 3652kb

input:

5
100 19 11
9 31 35 46 54 79 80 81 82 84 85 86 88 89 90 91 93 94 95
11 32 33 34 45 52 78 83 87 92 96
100 12 18
11 26 27 36 46 70 71 76 86 93 94 99
10 15 16 30 31 40 57 73 82 83 84 85 87 89 90 91 92 96
100 20 10
4 26 35 62 64 67 73 74 75 76 77 78 79 81 82 83 84 85 86 87
3 25 29 33 36 66 70 71 72 80
1...

output:

C
C
B
C
B

result:

ok 5 lines

Test #17:

score: 0
Accepted
time: 4ms
memory: 3500kb

input:

5
100 15 15
2 7 29 41 42 44 46 48 50 52 54 55 60 85 93
1 3 9 37 43 45 47 49 51 53 56 82 91 99 100
100 15 15
1 3 5 7 9 11 13 14 31 41 71 94 95 97 99
2 4 6 8 10 12 28 29 30 34 52 93 96 98 100
100 15 15
5 19 32 62 76 79 80 82 84 86 88 90 92 93 98
13 29 59 60 61 66 78 81 83 85 87 89 91 94 100
100 16 14
...

output:

R
B
C
B
C

result:

ok 5 lines

Test #18:

score: 0
Accepted
time: 4ms
memory: 3668kb

input:

20
1000 11 9
61 151 244 250 278 332 337 369 373 383 894
34 35 36 82 152 270 364 371 524
1000 11 9
44 94 95 96 98 100 102 103 294 575 796
93 97 99 101 104 297 665 815 897
1000 8 12
61 66 426 518 528 553 631 979
58 59 60 62 63 64 65 85 453 541 601 943
1000 8 12
205 271 306 407 441 811 964 968
181 252 ...

output:

R
B
B
B
C
B
B
B
B
B
C
B
R
B
B
B
C
B
B
R

result:

ok 20 lines

Test #19:

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

input:

20
1000 10 10
301 599 615 616 618 619 920 924 925 980
299 543 544 545 614 617 887 921 922 923
1000 10 10
154 309 540 659 704 904 905 906 907 973
151 152 153 371 561 660 661 662 903 908
1000 11 9
60 61 62 900 931 932 933 935 936 939 943
36 500 681 930 934 937 940 941 942
1000 11 9
257 258 259 976 980...

output:

R
C
B
B
B
B
B
R
C
C
C
R
R
C
C
C
R
R
B
R

result:

ok 20 lines

Test #20:

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

input:

20
1000 10 10
5 419 471 475 630 631 632 634 635 721
2 3 4 420 472 473 474 551 633 636
1000 10 10
221 224 317 318 319 338 652 762 905 977
219 220 222 223 230 320 506 639 664 795
1000 11 9
145 231 232 233 289 353 354 356 357 358 407
105 230 234 235 236 352 355 359 817
1000 14 6
520 759 803 804 805 806...

output:

R
B
C
B
B
B
R
B
R
B
B
B
B
C
C
B
B
B
B
R

result:

ok 20 lines

Test #21:

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

input:

5
9999999 150 150
37257 206259 234450 387580 578589 615372 673261 743334 743338 794572 833407 1408702 1572838 2019100 2019101 2019102 2081720 2098388 2132624 2976635 2980948 2980949 2980950 3001093 3001097 3014813 3016187 3016188 3016190 3016192 3016194 3016196 3016198 3016200 3016202 3016204 301620...

output:

B
B
C
B
C

result:

ok 5 lines

Test #22:

score: 0
Accepted
time: 3ms
memory: 3696kb

input:

5
9999999 146 154
233597 264788 264792 345011 345012 345013 345017 352995 352996 352997 353001 731941 737266 1075647 1090657 1212195 2034455 2119606 2149245 2149246 2149247 2170518 2170522 2170523 2170524 2170527 2170530 2170532 2170534 2170536 2170538 2170540 2170542 2170544 2170546 2170548 2170550...

output:

B
C
C
C
B

result:

ok 5 lines

Test #23:

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

input:

5
9999999 151 149
211277 256407 273121 273125 439630 518109 589143 641230 779454 780839 780840 780841 781054 1026218 1105707 1129751 1253130 1253134 1475664 1492357 1492358 1492360 1492362 1492364 1492366 1492368 1492370 1492372 1492374 1492376 1492378 1492380 1492382 1492384 1492386 1492388 1492390...

output:

R
B
B
R
R

result:

ok 5 lines

Test #24:

score: 0
Accepted
time: 7ms
memory: 3816kb

input:

15
1000000 402 598
6442 6777 6778 6779 7330 16610 16636 16637 16638 20242 20555 20559 24243 24375 37188 37216 37217 37218 37643 44575 45077 45081 45298 45299 45300 45626 51754 59650 59780 59781 59782 61935 63052 70074 70125 70126 70127 70242 70246 75875 77923 78337 93469 94143 94147 94609 97257 1078...

output:

R
B
C
B
C
C
B
B
R
R
B
B
B
C
C

result:

ok 15 lines

Test #25:

score: 0
Accepted
time: 5ms
memory: 4080kb

input:

5
1000000000 2446 2442
145613 1705596 2601367 2682534 2873537 2953597 2953598 2953599 2965967 3221057 3383559 7611830 8935977 9078024 9512246 9512250 9662102 10656933 12081997 13860946 13903101 14181624 14181628 14236051 16044777 16917514 17279177 17279181 19465751 19702320 20477024 20477028 2074225...

output:

C
C
R
C
B

result:

ok 5 lines

Test #26:

score: 0
Accepted
time: 6ms
memory: 4192kb

input:

5
1000000000 2445 2443
323359 650680 696403 818033 1698241 1803559 1972901 2227617 2400614 2624850 2651976 2859190 3379673 3631205 4244948 4441255 4671698 4910108 5014345 5301638 5413349 5597936 5858704 6281227 6401714 6811613 7104171 7177000 7280676 7334665 7870129 8334611 8646789 8782435 8963988 9...

output:

B
B
B
B
C

result:

ok 5 lines

Test #27:

score: 0
Accepted
time: 7ms
memory: 4160kb

input:

5
1000000000 2444 2444
21234 421451 504494 957488 1057673 1228404 1543011 1800118 1915469 2121356 2363569 2629049 3056060 3550050 3593070 3655700 3803376 3917217 3924620 4254473 4561524 4889002 5237610 5394299 5637398 5750969 5936810 6369030 6748591 7001087 7416532 7639299 7979330 8102208 8880464 89...

output:

R
B
B
C
R

result:

ok 5 lines

Test #28:

score: 0
Accepted
time: 35ms
memory: 10744kb

input:

1
400000001 64037 35964
113995 129073 132920 141251 155756 158097 312753 315554 315555 315556 326534 333401 359887 363144 383764 388941 395900 411019 417841 419652 424400 431494 577648 596464 601513 607152 621635 622260 622261 622262 625506 632685 665774 671722 703644 707003 710672 723044 738318 775...

output:

B

result:

ok single line: 'B'

Test #29:

score: 0
Accepted
time: 31ms
memory: 10084kb

input:

1
800000000 50005 49995
37954 162132 203077 235075 267270 286693 286697 317993 317997 330151 405790 423000 450553 499774 539729 539730 539731 555876 562731 576117 576121 588366 588367 588368 597894 677470 715608 761695 787307 787308 787309 795101 795105 837545 843807 893266 893270 916867 965405 9864...

output:

C

result:

ok single line: 'C'

Test #30:

score: -100
Memory Limit Exceeded

input:

1
1000000000 499984 500016
18340 20107 20206 20627 22255 26836 27301 28772 31749 31951 32310 33974 34449 35023 36126 36620 36799 36879 37636 39026 41742 41924 43978 45098 46228 49159 49551 54062 56382 56628 56747 57226 59557 59704 60500 63525 64802 65890 66588 67505 69434 71015 165174 167460 168283 ...

output:


result: