QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#432802 | #8722. 卡牌游戏 | A_zjzj | TL | 1744ms | 157840kb | C++14 | 2.2kb | 2024-06-07 17:52:42 | 2024-06-07 17:52:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=1e6+10;
int T,n,a[2][N];
map<tuple<int,int,vector<int>,vector<int>>,int>his;
int dfs(int op,int las=0){
auto cur=make_tuple(op,las,ary(a[0],1,n),ary(a[1],1,n));
if(his.count(cur))return his[cur];
for(int c:{0,1}){
if(count(a[c]+1,a[c]+1+n,0)==n)return his[cur]=c;
}
if(!las){
for(int i=1;i<=n;i++)if(a[op][i]){
a[op][i]--;
if(dfs(!op,i)==op)return a[op][i]++,his[cur]=op;
a[op][i]++;
}
return his[cur]=!op;
}else{
if(dfs(!op,0)==op)return his[cur]=op;
if(a[op][las]){
a[op][las]--;
if(dfs(!op,las)==op)return a[op][las]++,his[cur]=op;
a[op][las]++;
}
return his[cur]=!op;
}
}
void get(){
scanf("%d",&n);
for(int c:{0,1}){
for(int i=1;i<=n;i++)scanf("%d",&a[c][i]);
}
for(int c:{0,1}){
for(int i=1;i<=n;i++){
a[c][i]=min(a[c][i],a[!c][i]+1);
}
}
vector<int>x,y,z;
for(int i=1;i<=n;i++){
if(a[0][i]==a[1][i])y.push_back(a[0][i]+a[1][i]);
else if(a[0][i]<a[1][i])x.push_back(a[0][i]+a[1][i]);
else z.push_back(a[0][i]+a[1][i]);
}
sort(all(x)),reverse(all(x));
if(x.size()>1)x.resize(1);
sort(all(y)),reverse(all(y));
if(y.size()>2)y.resize(2);
sort(all(z)),reverse(all(z));
if(z.size()>2)z.resize(2);
vector<int>num;
for(int t:x)num.push_back(t);
for(int t:y)num.push_back(t);
for(int t:z)num.push_back(t);
sort(all(num)),num.erase(unique(all(num)),num.end());
vector<int>trs;
int cur=0;
for(int x:num){
for(cur++;cur%2!=x%2;cur++);
trs.push_back(cur);
}
n=0;
for(int t:x){
t=trs[lower_bound(all(num),t)-num.begin()];
a[0][++n]=(t-1)/2,a[1][n]=(t+1)/2;
}
for(int t:y){
t=trs[lower_bound(all(num),t)-num.begin()];
a[0][++n]=t/2,a[1][n]=t/2;
}
for(int t:z){
t=trs[lower_bound(all(num),t)-num.begin()];
a[0][++n]=(t+1)/2,a[1][n]=(t-1)/2;
}
// debug(ary(a[0],1,n));
// debug(ary(a[1],1,n));
puts(dfs(0)?"Bob":"Alice");
}
int main(){
for(scanf("%d",&T);T--;)get();
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
详细
Test #1:
score: 100
Accepted
time: 1132ms
memory: 118568kb
input:
5 1 100 100 2 1 1 1 1 2 1 1 0 1 3 1 1 4 5 1 4 10 116 104 101 114 101 32 97 114 101 32 102 105 118 101 32 99 97 115 101 115
output:
Alice Bob Alice Alice Alice
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 348ms
memory: 5760kb
input:
1000000 1 901418150 815121916 1 455099013 31761433 1 46418945 11466871 1 709189476 658667824 1 977821005 511405192 1 843598992 501074199 1 638564514 680433292 1 994431111 584582554 1 452689372 642414314 1 863578235 135133204 1 438404803 67246919 1 492858783 447116205 1 723252212 948645336 1 19105046...
output:
Bob Bob Bob Bob Bob Bob Alice Bob Alice Bob Bob Bob Alice Alice Alice Alice Bob Alice Alice Alice Bob Bob Alice Bob Bob Alice Bob Bob Alice Alice Alice Alice Bob Bob Bob Bob Bob Bob Bob Alice Alice Alice Bob Bob Bob Bob Alice Alice Bob Bob Alice Bob Bob Bob Bob Bob Alice Alice Alice Alice Alice Alic...
result:
ok 1000000 lines
Test #3:
score: 0
Accepted
time: 290ms
memory: 5796kb
input:
500000 2 373642622 454169042 952441803 417874927 2 71762287 551454259 538969462 292052813 2 531091498 645143315 755275238 984088455 2 936400451 948257592 457379982 873148501 2 45309968 731348143 181471857 558039453 2 931056469 394825335 620380282 26893900 2 69376673 489359332 614858046 635100016 2 5...
output:
Alice Alice Alice Bob Alice Bob Alice Alice Alice Bob Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alic...
result:
ok 500000 lines
Test #4:
score: 0
Accepted
time: 277ms
memory: 5820kb
input:
333334 3 255932511 789675559 760669141 384728982 140424908 361439344 3 393719043 379329282 446687639 515372386 704177992 688441074 3 939269095 492018656 596461367 570763162 161714447 384092911 3 304150759 350079205 296791887 54574629 804917425 311704304 3 120533843 787668201 243944555 281070757 3118...
output:
Alice Alice Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Bob Alice Alice Bob Alice Alice Alice Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Bob Alice Alice Alice Alice Bob Alice Al...
result:
ok 333334 lines
Test #5:
score: 0
Accepted
time: 262ms
memory: 6064kb
input:
250000 4 433189692 125182076 154608701 309612754 522048869 157942182 257538154 148757376 4 932599775 953264671 532072322 109408648 243015330 466422620 347709852 523909322 4 779016547 171920667 474134651 198758440 218117745 477480878 358050786 891482000 4 835254525 380944361 650059555 954568851 94728...
output:
Alice Bob Bob Alice Alice Alice Alice Alice Bob Bob Bob Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Bob Bob Alice Bob Bob Bob Alice Bob Alice Alice Bob Alice Alice Alice Bob Alice Alice Bob Bob Bob Alice Bob Bob Alice Bob Alice Alice Alice ...
result:
ok 250000 lines
Test #6:
score: 0
Accepted
time: 239ms
memory: 5820kb
input:
200000 5 315479581 124252105 179952043 446844829 780837560 954336048 880492165 785040744 77109657 486885376 5 754808995 829908259 358202421 330167945 449755992 539371459 461093031 812475269 420738799 974016054 5 893157388 27096064 181378986 679253230 392611044 911184149 544888624 949932667 633194309...
output:
Alice Bob Alice Alice Alice Alice Alice Bob Alice Alice Bob Alice Alice Alice Bob Bob Bob Alice Alice Bob Alice Alice Alice Alice Bob Bob Alice Bob Alice Bob Bob Bob Alice Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Alice Alice Bob Alice Bob Bob Alice Alice Alice Bob Alice Bob ...
result:
ok 200000 lines
Test #7:
score: 0
Accepted
time: 229ms
memory: 6056kb
input:
166667 6 787704054 754725914 573891604 657705832 629075344 187757098 796688644 561572949 312543334 300429230 435788130 22385714 6 464180683 270559705 512723125 317525900 680776345 929062617 238039721 101041215 959796342 765518522 95721291 124666319 6 937568865 977562099 503758752 600693233 482891755...
output:
Alice Alice Bob Alice Alice Bob Alice Alice Alice Bob Alice Alice Alice Alice Bob Alice Alice Alice Alice Bob Alice Bob Bob Bob Alice Alice Alice Alice Bob Bob Alice Alice Alice Alice Alice Bob Bob Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Bob ...
result:
ok 166667 lines
Test #8:
score: 0
Accepted
time: 211ms
memory: 5840kb
input:
142858 7 669993943 458828651 599234946 205003324 182345837 989301423 762016619 565412311 579090223 208642144 933814220 974625469 726738333 720019121 7 224386186 105343720 185295808 99799082 536061877 283693326 275870967 389607162 162417396 598490187 648854654 114509431 282358088 913068064 7 61490646...
output:
Bob Alice Alice Alice Alice Alice Alice Bob Alice Alice Bob Alice Bob Bob Alice Alice Bob Alice Alice Alice Bob Alice Bob Alice Bob Bob Alice Bob Bob Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Bob Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Al...
result:
ok 142858 lines
Test #9:
score: 0
Accepted
time: 211ms
memory: 5876kb
input:
125000 8 552283832 89302459 288141798 710831619 30583621 790845747 59852554 136743470 997699491 301640204 31112026 862166501 218495514 504719880 128369591 678173109 8 656495120 758098425 223854527 69432210 629817788 942776057 357457949 583254104 701474939 389992655 907020724 399319835 579974579 9262...
output:
Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Bob Bob Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Bob Bob Al...
result:
ok 125000 lines
Test #10:
score: 0
Accepted
time: 205ms
memory: 6096kb
input:
111112 9 729541013 88372488 682081360 258129110 878821407 297422778 62721199 90569951 839050299 135019377 319157478 558614617 790518782 167398268 577668719 315381698 966739056 904095993 9 625868334 11473484 971398763 680974958 241084925 468605657 443130759 238053542 472276082 181495123 460154086 979...
output:
Alice Alice Alice Alice Alice Bob Alice Bob Bob Alice Alice Alice Bob Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Bob Alice Bob Alice Alice Al...
result:
ok 111112 lines
Test #11:
score: 0
Accepted
time: 201ms
memory: 6096kb
input:
100000 10 805513144 16228409 293487744 138613792 904651590 443174087 579288498 179297759 92837851 983905980 38998401 266085559 471510400 649258082 244678415 503924246 219903162 762760972 728185679 299473031 10 832979751 172561293 280283392 787972981 793926222 737031746 557170071 125596289 496666505 ...
output:
Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Bob Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Alice Bob Alice Alice Alice Alice Alice Bob Alice Alice Bob Bob Alice Bob Bob Alice Alice Alice Bob Bob Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Al...
result:
ok 100000 lines
Test #12:
score: 0
Accepted
time: 155ms
memory: 5792kb
input:
10000 100 258451417 131461228 90882155 515132461 142193666 268703262 438399665 496441726 272155240 488884603 434294700 46665933 85686327 427508332 924703210 940706911 435760562 530430234 883161948 143892 380020584 457415756 724899860 153927087 496191785 779583285 610659939 499798744 516835198 856344...
output:
Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Bob Bob Alice Alice Alice Alice Alice Bob Alice Bob Bob Bob Alice ...
result:
ok 10000 lines
Test #13:
score: 0
Accepted
time: 165ms
memory: 5832kb
input:
1000 1000 818764393 365785354 182329463 505722718 170434181 271553309 682902243 969587436 357926604 726853357 365462194 450888086 623408110 207066774 856645299 759038423 7909179 766781340 606491108 870056833 795101174 962703326 886499707 948293516 722050066 121757393 790355795 935584955 699241546 10...
output:
Alice Bob Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Bob Alice Alice Alice Bob Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice ...
result:
ok 1000 lines
Test #14:
score: 0
Accepted
time: 171ms
memory: 5912kb
input:
100 10000 134585047 198253791 832787942 379503394 759930568 78098848 856344096 687752429 955359447 604231866 633132058 917017611 871376871 690456996 647742795 662264486 595368882 913081962 176310084 166738544 140290705 677038583 562494362 872653067 941311074 417588015 273081597 220145645 394812742 6...
output:
Bob Bob Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Al...
result:
ok 100 lines
Test #15:
score: 0
Accepted
time: 176ms
memory: 6452kb
input:
10 100000 695714444 813918810 630808478 11366687 728101884 313790123 336178036 917835491 75687191 293774105 312834569 474048791 468299389 799170568 641239437 339199025 438895973 600678429 484096403 877169248 36096533 155063171 926295418 785171522 468066843 779290770 735443817 505563889 804173005 698...
output:
Alice Alice Alice Bob Bob Alice Alice Bob Bob Bob
result:
ok 10 lines
Test #16:
score: 0
Accepted
time: 196ms
memory: 15188kb
input:
1 1000000 810947263 242717000 7327146 838843348 890067548 804305071 21918222 802185588 285698523 895089055 186939209 279451727 107834740 929947555 476318383 586385736 770100990 987173872 722315109 224531103 794320253 495864614 140786321 632520516 958019853 519002273 560006689 126550712 433800823 503...
output:
Bob
result:
ok single line: 'Bob'
Test #17:
score: 0
Accepted
time: 110ms
memory: 15920kb
input:
1 1000000 1 0 1 0 0 1 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 1 0 0 ...
output:
Bob
result:
ok single line: 'Bob'
Test #18:
score: 0
Accepted
time: 104ms
memory: 15140kb
input:
1 1000000 2 1 1 0 0 2 0 1 0 2 2 1 1 0 1 0 2 2 0 2 0 0 1 0 2 2 1 1 2 2 0 2 2 2 1 0 0 2 0 1 1 2 0 2 2 0 2 1 1 0 0 1 1 2 2 2 0 2 2 1 2 2 0 1 2 0 0 2 2 1 2 1 1 0 2 1 2 0 0 2 0 2 0 0 0 0 1 0 2 1 1 1 0 2 1 0 1 0 2 1 2 0 2 0 0 0 2 2 0 0 1 1 0 2 2 0 0 0 2 2 0 2 0 2 2 1 1 2 2 2 1 2 1 2 2 1 1 0 2 1 1 0 1 1 2 ...
output:
Bob
result:
ok single line: 'Bob'
Test #19:
score: 0
Accepted
time: 186ms
memory: 8296kb
input:
123836 1 1 1 2 0 1 0 1 2 0 1 1 0 2 0 1 1 1 2 1 0 0 1 2 1 0 1 0 2 1 0 1 1 2 1 1 0 1 2 1 1 1 0 2 1 1 1 1 3 0 0 1 0 0 1 3 0 0 1 0 1 0 3 0 0 1 0 1 1 3 0 0 1 1 0 0 3 0 0 1 1 0 1 3 0 0 1 1 1 0 3 0 0 1 1 1 1 3 0 1 0 0 0 1 3 0 1 0 0 1 0 3 0 1 0 0 1 1 3 0 1 0 1 0 0 3 0 1 0 1 0 1 3 0 1 0 1 1 0 3 0 1 0 1 1 1 3...
output:
Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Bob Alice Alice Alice Alice Alice Bob Bob Al...
result:
ok 123836 lines
Test #20:
score: 0
Accepted
time: 484ms
memory: 43256kb
input:
178944 1 1 1 1 1 2 1 2 1 1 2 2 2 0 1 0 1 2 0 1 0 2 2 0 1 1 0 2 0 1 1 1 2 0 1 1 2 2 0 1 2 0 2 0 1 2 1 2 0 1 2 2 2 0 2 0 1 2 0 2 0 2 2 0 2 1 0 2 0 2 1 1 2 0 2 1 2 2 0 2 2 0 2 0 2 2 1 2 0 2 2 2 2 1 0 0 1 2 1 0 0 2 2 1 0 1 0 2 1 0 1 1 2 1 0 1 2 2 1 0 2 0 2 1 0 2 1 2 1 0 2 2 2 1 1 0 1 2 1 1 0 2 2 1 1 1 0...
output:
Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Bob Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice ...
result:
ok 178944 lines
Test #21:
score: 0
Accepted
time: 1744ms
memory: 157840kb
input:
214734 1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 2 0 1 0 1 2 0 1 0 2 2 0 1 0 3 2 0 1 1 0 2 0 1 1 1 2 0 1 1 2 2 0 1 1 3 2 0 1 2 0 2 0 1 2 1 2 0 1 2 2 2 0 1 2 3 2 0 1 3 0 2 0 1 3 1 2 0 1 3 2 2 0 1 3 3 2 0 2 0 1 2 0 2 0 2 2 0 2 0 3 2 0 2 1 0 2 0 2 1 1 2 0 2 1 2 2 0 2 1 3 2 0 2 2 0 2 0 2 2 1...
output:
Alice Alice Alice Bob Alice Alice Bob Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice ...
result:
ok 214734 lines
Test #22:
score: 0
Accepted
time: 266ms
memory: 14928kb
input:
254144 1 1 1 1 1 2 1 1 3 1 1 4 1 2 1 1 2 2 1 2 3 1 2 4 1 3 1 1 3 2 1 3 3 1 3 4 1 4 1 1 4 2 1 4 3 1 4 4 2 0 1 0 1 2 0 1 0 2 2 0 1 0 3 2 0 1 0 4 2 0 1 1 0 2 0 1 1 1 2 0 1 1 2 2 0 1 1 3 2 0 1 1 4 2 0 1 2 0 2 0 1 2 1 2 0 1 2 2 2 0 1 2 3 2 0 1 2 4 2 0 1 3 0 2 0 1 3 1 2 0 1 3 2 2 0 1 3 3 2 0 1 3 4 2 0 1 4...
output:
Alice Alice Alice Alice Bob Alice Alice Alice Bob Bob Alice Alice Bob Bob Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Al...
result:
ok 254144 lines
Test #23:
score: 0
Accepted
time: 256ms
memory: 14616kb
input:
262187 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 2 1 1 2 2 1 2 3 1 2 4 1 2 5 1 3 1 1 3 2 1 3 3 1 3 4 1 3 5 1 4 1 1 4 2 1 4 3 1 4 4 1 4 5 1 5 1 1 5 2 1 5 3 1 5 4 1 5 5 2 0 1 0 1 2 0 1 0 2 2 0 1 0 3 2 0 1 0 4 2 0 1 0 5 2 0 1 1 0 2 0 1 1 1 2 0 1 1 2 2 0 1 1 3 2 0 1 1 4 2 0 1 1 5 2 0 1 2 0 2 0 1 2 1 2 0 1 2 2 2 0...
output:
Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Bob Bob Alice Alice Alice Bob Bob Bob Alice Alice Bob Bob Bob Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Al...
result:
ok 262187 lines
Test #24:
score: -100
Time Limit Exceeded
input:
140974 1 981241784 985495911 1 381983544 381983544 1 742839650 603202993 2 683536728 0 0 830012704 2 0 620715140 211047202 642526535 2 0 776943391 902236202 776943391 2 0 968124432 430302156 748936590 2 0 777548137 0 871216897 2 310832284 0 310832284 0 2 0 859186255 0 752655474 2 303238506 864307428...
output:
Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Bob Alice Alice Bob Bob Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Bob Bob Alice Alice Bob Bob Alice Alice ...