QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#53739 | #2102. Gra w kółko | Appleblue17# | ML | 34ms | 10936kb | C++14 | 4.0kb | 2022-10-05 21:16:40 | 2022-10-05 21:16:42 |
Judging History
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(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;
exit(0);
}
// 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(){
// 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;
}
}
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]});
}
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: 0ms
memory: 3748kb
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: 2ms
memory: 3648kb
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: 0ms
memory: 3580kb
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: 2ms
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: 2ms
memory: 3656kb
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: 2ms
memory: 3560kb
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: 0ms
memory: 3576kb
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: 3580kb
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: 2ms
memory: 3652kb
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: 3576kb
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: 2ms
memory: 3656kb
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: 2ms
memory: 3580kb
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: 2ms
memory: 3744kb
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: 2ms
memory: 3692kb
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: 2ms
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: 2ms
memory: 3660kb
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: 2ms
memory: 3696kb
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: 2ms
memory: 3644kb
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: 3ms
memory: 3564kb
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: 3648kb
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: 3ms
memory: 3544kb
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: 2ms
memory: 3720kb
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: 4ms
memory: 3704kb
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: 10ms
memory: 3664kb
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: 3992kb
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: 11ms
memory: 4276kb
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: 11ms
memory: 4220kb
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: 34ms
memory: 10936kb
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: 32ms
memory: 10088kb
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 ...