QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#682527 | #8823. Game: Battle of Menjis | ucup-team4352# | AC ✓ | 246ms | 6204kb | C++23 | 1.2kb | 2024-10-27 15:51:56 | 2024-10-27 15:51:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int T,n,k,a[maxn],b[maxn];
const int maxm=6e6+5;
int ch[maxm][2],tot,sum[maxm];
void clear() {
for(int i=0;i<=tot;++i) ch[i][0]=ch[i][1]=sum[i]=0;
tot=0;
}
void insert(int now,int p,int x) {
sum[now]++;
if(p==-1) return;
int w=(x>>p)&1;
if(!ch[now][w]) ch[now][w]=++tot;
insert(ch[now][w],p-1,x);
}
void del(int now,int p,int x) {
sum[now]--;
if(p==-1) return;
int w=(x>>p)&1;
del(ch[now][w],p-1,x);
}
int query(int now,int p,int x) {
if(p==-1) return x;
int w=(x>>p)&1;
if(ch[now][w]&&sum[ch[now][w]]) return query(ch[now][w],p-1,x^(w<<p));
else return query(ch[now][!w],p-1,x|(1<<p));
}
int main() {
//ios::sync_with_stdio(0);
//cin.tie(0);
cin>>T;
while(T--) {
cin>>n>>k;
int tmp=0;
for(int i=1;i<=n;++i) {
cin>>a[i];
tmp^=a[i];
if(a[i]==0) b[i]=-1;
else b[i]=(a[i]^(a[i]-1)),insert(0,30,b[i]);
}
int ans=0;
for(int i=1;i<=n;++i) {
int now=tmp^a[i]^(a[i]+1);
if(a[i]) del(0,30,b[i]);
insert(0,30,a[i]^(a[i]+1));
ans=max(ans,query(0,30,now));
del(0,30,a[i]^(a[i]+1));
if(a[i]) insert(0,30,b[i]);
}
cout<<ans<<'\n';
clear();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5760kb
input:
4 2 3 1 1 4 4 0 0 0 0 4 1 1 2 4 8 13 5 1 1 4 5 1 4 1 9 1 9 8 1 0
output:
0 0 9 11
result:
ok 4 number(s): "0 0 9 11"
Test #2:
score: 0
Accepted
time: 164ms
memory: 5688kb
input:
100000 1 5 0 4 5 4 4 3 5 5 2 0 1 7 5 4 4 1 6 4 4 4 1 5 3 2 2 1 1 3 1 5 4 0 2 4 0 3 2 2 1 7 3 1 2 1 6 2 4 5 1 3 1 3 7 0 4 4 7 5 4 4 3 3 1 1 5 1 3 3 3 2 3 7 4 4 1 3 1 0 5 5 3 6 2 3 6 3 3 1 2 6 6 4 4 5 4 1 3 2 1 4 4 4 5 0 1 6 5 4 5 0 7 7 5 2 4 4 0 5 1 7 0 2 6 0 3 4 5 2 3 2 3 4 3 3 2 1 0 1 2 2 6 5 5 1 6...
output:
0 2 7 2 3 0 1 3 6 5 4 4 2 5 3 0 7 2 0 3 0 2 5 4 3 4 7 0 3 2 4 4 4 2 4 6 1 3 2 7 4 7 4 6 2 4 4 3 7 0 2 2 1 0 6 7 0 0 1 7 1 3 3 6 2 1 5 5 5 1 6 4 1 2 0 7 1 4 3 6 7 7 0 1 7 0 0 4 0 4 7 7 7 4 6 2 5 4 7 4 1 6 4 4 3 4 7 5 4 4 3 6 1 2 5 4 2 1 1 0 0 0 0 6 1 3 4 0 1 4 6 3 1 3 5 1 0 6 3 2 1 4 5 2 1 2 2 7 6 7 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 171ms
memory: 5692kb
input:
10000 45 41 124 126 8 59 3 89 75 2 88 65 17 107 90 92 113 103 122 7 87 89 61 78 4 27 61 117 9 122 40 114 80 54 63 111 19 4 89 77 99 12 93 28 34 106 75 47 50 49 52 96 35 99 61 126 80 122 33 96 67 99 44 29 4 126 64 0 111 31 84 8 52 16 112 103 85 13 50 4 42 70 76 121 96 96 3 21 118 116 50 90 63 15 69 0...
output:
55 7 110 84 12 57 76 48 4 76 8 97 37 18 72 6 37 70 20 17 55 31 118 118 3 78 67 62 18 97 14 24 86 49 81 33 84 95 78 47 80 51 64 55 86 105 96 64 67 29 14 42 94 49 34 78 27 5 8 59 68 43 23 108 78 67 99 84 109 5 75 29 48 42 102 37 87 68 81 87 101 111 10 34 106 90 52 8 67 37 36 9 71 76 79 108 25 49 107 9...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 245ms
memory: 3760kb
input:
100 4991 710173979 194350399 308253661 453535140 859535540 237118582 491883070 203713206 876045568 179614490 762427255 600586096 195805957 619372254 837564280 46030125 818656915 624958658 579965169 315157532 507369398 223649057 730321515 87001797 103914474 146001643 169828188 694735418 411534273 158...
output:
895973929 644710414 718127976 764287680 427180528 89428087 633652199 202995551 1019972853 492532509 856424472 740558823 71451464 522956950 559048723 352180449 357679270 737527068 105530653 703884103 744126411 991785031 92210383 423071396 825321389 911136722 406765701 757424811 1045423355 312227835 6...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 245ms
memory: 4480kb
input:
5 99923 692526850 715084131 984147203 17386228 785452545 982653579 705503250 519275489 706775608 799238095 351240081 520684482 896504393 520155812 883104115 42870024 735387097 365091799 214533775 762045747 566889361 577707360 474682304 386471939 908932293 291557432 740983423 444227029 754037318 5809...
output:
566935826 841956871 997917453 927747273 280103635
result:
ok 5 number(s): "566935826 841956871 997917453 927747273 280103635"
Test #6:
score: 0
Accepted
time: 164ms
memory: 5760kb
input:
100000 1 5 3 2 1 0 3 4 1 0 4 7 6 3 1 4 0 5 5 3 0 0 7 7 7 5 4 3 6 7 7 0 1 1 2 3 5 5 0 0 4 4 4 0 4 0 5 2 7 7 7 0 7 2 1 2 4 2 3 7 2 4 2 6 0 3 7 2 5 7 5 5 2 7 7 2 0 0 1 1 7 2 2 3 0 2 1 7 0 4 1 0 3 4 7 4 5 7 7 3 3 4 1 0 0 7 0 1 1 0 5 3 7 0 3 3 6 3 4 2 4 0 1 1 0 2 5 2 6 1 1 0 4 5 3 0 4 5 1 2 4 3 3 7 2 3 1...
output:
3 3 5 1 7 5 2 5 0 0 4 5 2 2 2 7 3 7 0 0 7 0 1 4 0 4 0 2 4 6 0 0 2 7 1 0 3 1 1 6 3 3 4 0 4 0 4 0 0 0 0 1 3 3 1 3 0 7 4 3 0 3 4 0 7 0 7 5 3 3 3 3 7 4 0 3 7 2 4 1 0 3 2 4 5 7 3 7 3 7 1 6 3 1 3 7 6 2 3 4 1 6 0 2 1 0 4 1 4 0 6 3 1 0 5 0 7 7 7 7 0 0 6 0 3 0 5 4 3 0 3 0 7 4 3 4 0 6 7 2 0 5 7 2 7 6 7 7 3 1 ...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 170ms
memory: 5624kb
input:
10000 45 41 120 28 111 121 96 64 11 24 31 55 0 24 0 127 16 15 79 127 0 0 127 64 31 10 95 0 0 96 71 40 0 123 31 11 32 32 0 11 76 127 0 96 47 100 0 49 49 6 64 96 64 32 63 127 112 32 64 127 63 13 124 71 8 0 47 0 64 119 127 55 15 31 12 23 15 112 112 71 0 63 0 127 127 0 0 122 111 96 19 80 26 0 96 64 63 0...
output:
39 119 1 101 109 22 67 95 117 16 93 74 14 38 47 12 46 85 94 24 121 11 57 30 101 20 1 28 58 88 82 86 119 118 5 42 0 46 12 107 100 116 32 94 89 15 59 61 19 104 87 35 98 88 109 81 86 72 91 7 23 31 20 102 122 59 107 95 44 98 56 120 73 77 46 71 77 22 34 74 98 4 94 50 66 109 14 94 48 109 19 83 82 50 111 2...
result:
ok 10000 numbers
Test #8:
score: 0
Accepted
time: 234ms
memory: 3740kb
input:
100 4981 345654103 271056895 536870911 473956351 229113855 534118400 496205823 362817983 238026751 67108864 476615359 252973055 426702360 95525311 7733247 119537663 16777216 269481984 536870911 328204288 67108863 165849087 22020095 536870911 257982463 268435456 379563839 158931327 401113088 10616831...
output:
375646588 196120712 530324071 389523587 258272848 96526039 389694507 21615298 231064942 120412838 40426797 91846174 346651816 274396025 532233855 125617615 15515680 463100220 6712977 393632829 216352692 18895979 452122769 513009110 172803659 433540024 146587264 499919020 399197579 422726691 22109121...
result:
ok 100 numbers
Test #9:
score: 0
Accepted
time: 246ms
memory: 6204kb
input:
5 99965 925086677 462946303 195362816 440926207 490536960 459014143 489057920 417644544 67108863 268435455 214024191 271622627 159776767 268435455 262144000 514392063 287886847 257949696 247544320 377024384 130878659 390598655 355024896 405302515 302252032 391592447 124878335 394919936 385875967 692...
output:
282456931 529494087 271489722 300788235 290503299
result:
ok 5 number(s): "282456931 529494087 271489722 300788235 290503299"
Test #10:
score: 0
Accepted
time: 216ms
memory: 5788kb
input:
100 5000 1000000000 24226 18044 966 17980 3578 874 15232 5874 66263 27100 66251 16342 32006 12184 65662 24982 22510 30690 2196 14986 66121 9236 20802 13646 26192 65764 18194 29370 4922 29284 25344 9766 16026 11740 3008 16472 16276 20674 22078 4720 65738 30310 10030 26570 66468 18682 3142 66125 2014 ...
output:
6065 455436 5353175 1780645 493241 904 65737047 932834 20756929 141438 135369 4813 9189 2016035 1803189 104752 54059 190233 7226353 205342 877968 6836583 9116 25705 15270003 459643 12249 11866574 27640676 160246 45502 70702851 1066977 315843 127161 25020 2082725 18271 4203107 20132554 123 43126 5409...
result:
ok 100 numbers
Test #11:
score: 0
Accepted
time: 223ms
memory: 4048kb
input:
10 50000 1000000000 14945976 12846736 277398 7075128 12533968 13805792 7120706 3136112 1102332 14628918 33556221 9626418 3073970 7379354 4754722 14323124 8119284 13341952 4639522 33559898 8455698 33555019 2750888 15445086 12632228 112896 257198 3337600 1462910 768220 10491396 33562170 10123992 33560...
output:
16433166 26883384 14024 4484923 2655078 105987 31134 112599024 5899713 127581034
result:
ok 10 numbers
Test #12:
score: 0
Accepted
time: 218ms
memory: 4424kb
input:
5 100000 1000000000 39282 1066015 1062466 272082 58228 1049517 315024 98990 70944 149646 483724 147520 404642 302334 329860 146090 200222 197060 240026 214656 36610 310816 229774 238514 360684 403142 423786 474384 1049273 1063613 1060442 429178 405908 207638 227118 360282 1067663 232772 53846 487718...
output:
11959 81687 248175012 31990 3479
result:
ok 5 number(s): "11959 81687 248175012 31990 3479"
Extra Test:
score: 0
Extra Test Passed