QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468908 | #1899. Maximaze XOR sum | nhtd211008 | AC ✓ | 906ms | 5392kb | C++20 | 1.6kb | 2024-07-09 02:46:18 | 2024-07-09 02:46:18 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define bit(x,i) ((x>>i)&1)
vector<int> merge(vector<int> a,vector<int> b){
vector<int> res;
set_symmetric_difference(a.begin(),a.end(),b.begin(),b.end(),back_inserter(res));
return res;
}
struct xor_basis{
long long basis[60]={0};
vector<int> trace[60];
int cnt=0;
void insert(long long x,vector<int> a){
for(int i=59;i>=0;i--)if(bit(x,i)){
if(basis[i]){
x^=basis[i];
a=merge(a,trace[i]);
}
else{
cnt++;
basis[i]=x;
trace[i].swap(a);
return;
}
}
}
} sus;
const int maxn=1e5+1;
long long a[maxn],b[maxn],A,B;
int n;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
A^=a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
B^=b[i];
sus.insert(a[i]^b[i],{i});
}
vector<int> res;
for(int i=59;i>=0;i--)if(sus.basis[i]){
if(bit(A,i) && bit(B,i)) continue;
if(bit(A,i)==0 && bit(B,i)==0){
A^=sus.basis[i];
B^=sus.basis[i];
res=merge(res,sus.trace[i]);
}
else{
long long x=sus.basis[i]^(1LL<<i);
vector<int> tmp=sus.trace[i];
sus.basis[i]=0;
sus.trace[i].clear();
sus.insert(x,tmp);
}
}
cout<<A+B<<" "<<res.size()<<'\n';
for(int i:res) cout<<i<<" ";
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 2 1 4 4 0 4
output:
7 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
10 12 0 4 3 1 1 12 3 11 11 3 3 14 6 14 15 1 15 5 2
output:
26 1 1
result:
ok n=10
Test #4:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
50 9 27 19 1 31 10 2 7 25 26 12 25 15 18 11 15 30 25 31 2 5 30 8 18 8 17 14 2 17 7 26 26 10 25 26 5 3 5 1 17 18 12 4 17 14 19 30 30 20 2 13 18 3 8 18 11 31 20 21 14 17 29 31 2 5 28 31 17 10 13 6 10 22 18 10 2 0 15 7 14 4 15 25 10 3 30 3 21 0 12 11 19 4 16 27 10 26 3 2 5
output:
35 0
result:
ok n=50
Test #5:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
100 50 13 42 41 8 21 50 18 21 50 9 27 51 10 43 26 29 6 52 44 52 19 39 47 59 35 42 6 27 41 8 25 32 32 45 18 57 5 46 32 60 24 63 56 31 32 58 15 0 36 31 33 31 50 14 45 31 27 15 55 8 53 10 5 8 24 15 35 45 34 16 31 44 51 34 13 30 49 0 4 62 6 8 30 44 29 59 60 45 40 1 0 40 29 35 18 42 52 15 28 35 43 24 14 ...
output:
77 3 1 2 3
result:
ok n=100
Test #6:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
239 102 34 53 67 127 99 16 79 25 9 34 91 63 46 1 27 47 66 54 90 93 10 60 118 110 27 5 95 62 99 117 28 90 33 101 69 7 104 33 10 57 32 106 42 28 5 117 125 15 38 107 107 36 103 103 115 34 127 123 37 3 123 43 40 118 57 112 53 94 110 54 26 81 33 94 55 25 45 61 4 55 67 27 10 91 102 53 101 109 109 60 73 8 ...
output:
243 5 1 2 3 4 6
result:
ok n=239
Test #7:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
322 167 3 23 89 165 131 48 207 116 214 246 1 39 79 196 84 123 132 211 177 76 209 197 5 30 214 29 193 149 245 196 90 253 213 134 202 195 226 147 13 249 202 254 165 214 1 65 23 52 62 184 108 16 252 33 177 14 250 34 119 243 187 195 83 41 7 240 95 62 104 248 184 101 174 17 254 243 108 209 215 227 120 18...
output:
397 2 5 7
result:
ok n=322
Test #8:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
654 456 150 36 391 6 195 17 37 56 92 403 225 374 294 447 267 112 149 125 225 485 86 262 25 301 197 108 91 176 375 18 453 109 434 48 358 116 240 80 451 364 352 468 340 270 101 110 264 167 277 165 189 410 187 87 457 476 341 305 372 119 22 313 379 7 485 325 143 320 477 385 212 358 459 493 98 211 179 22...
output:
612 2 2 5
result:
ok n=654
Test #9:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
1000 141 295 799 239 546 573 90 163 285 348 277 944 836 925 584 691 480 831 174 427 574 36 326 125 559 83 467 880 136 116 349 946 419 87 174 977 989 877 726 66 22 333 424 989 564 561 571 94 416 886 361 742 454 32 83 121 666 339 219 638 270 731 552 834 925 933 294 629 708 580 259 427 387 365 947 220 ...
output:
1973 3 2 7 9
result:
ok n=1000
Test #10:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
1234 261 1657 517 1483 1960 89 1370 670 410 1340 1722 1381 995 1916 604 2043 779 1686 59 1953 1951 1966 150 1402 688 1545 112 1806 595 912 1553 1739 1570 339 1411 1151 953 4 1301 1503 826 120 476 1796 970 1066 1069 745 17 1464 1061 1006 702 356 1569 1112 769 1428 1862 1742 271 850 506 1758 674 1740 ...
output:
2771 7 1 2 3 5 8 9 10
result:
ok n=1234
Test #11:
score: 0
Accepted
time: 14ms
memory: 3680kb
input:
4321 954480449 587144652 757102525 355665537 828579167 331077434 432524612 696971489 994830414 712338630 893352505 861729750 502105584 1035097357 411845405 686198569 310059262 611729823 534618751 260487378 956262276 516622722 333379461 165343106 889332064 1032610733 563086441 612113690 937039558 168...
output:
1905476326 15 4 7 8 9 10 11 13 15 19 22 23 24 25 26 27
result:
ok n=4321
Test #12:
score: 0
Accepted
time: 39ms
memory: 3968kb
input:
7890 167365278745 53574745863 1083471078178 94877662306 414150779087 732017494615 268662798673 640482866772 813746165313 1039118737841 317126232364 273209176527 260850168401 122195402366 173566316456 703789564575 840725477414 416413225738 483521349439 1015327498161 438272982188 180451885829 54687593...
output:
1241550719429 19 2 3 7 8 9 10 12 13 17 18 19 20 21 24 25 32 35 40 42
result:
ok n=7890
Test #13:
score: 0
Accepted
time: 69ms
memory: 3716kb
input:
10000 1024699458171845 273191988760302 672954995688326 856568833018077 965082229777704 277750079399023 667877391291263 435567952575490 586753361866430 328361268020042 1013607754170263 601702869301405 1104383095207561 1094567873246657 910010660363394 921121581843645 908188549630208 527368341706711 95...
output:
2243904366424282 30 3 5 6 7 9 10 11 13 14 16 18 20 23 25 26 27 28 32 33 35 36 37 38 39 41 43 44 46 47 49
result:
ok n=10000
Test #14:
score: 0
Accepted
time: 474ms
memory: 4424kb
input:
54321 287544013263348545 413574927091445621 153643489008592756 341000867154444534 452141620779135825 418037037459393872 437986525649658049 372212963309521161 257015343258028217 387140473042153213 458887496977630175 395676640510290584 422614008331646164 149326923431862672 342772251032951733 551391483...
output:
868733566987466643 26 2 3 5 6 8 9 10 13 14 16 17 19 22 26 30 32 33 34 35 36 38 44 48 51 54 55
result:
ok n=54321
Test #15:
score: 0
Accepted
time: 901ms
memory: 5392kb
input:
100000 841498407491613453 905351872506134827 637459962220586234 155015946330061417 375956423605355233 882762322851119382 248810585943451875 275218210487324308 298207666026610255 164819846716632447 851272972445309356 371928988877796479 423315776354517843 647936740264782090 379052530058820048 75427528...
output:
1659763625722214659 25 1 5 6 9 11 20 21 25 26 30 31 32 34 37 40 41 42 45 46 47 48 49 51 56 58
result:
ok n=100000
Test #16:
score: 0
Accepted
time: 906ms
memory: 5328kb
input:
100000 842324650669696877 564952864934459472 377394673959590984 163128152355690893 961366116879671787 899738512395598156 136317789673223855 690049913535541000 894276073102320211 203253982998936629 723989087119569797 578879220494132023 63279924997350639 414155802849417030 352229079985823071 543157258...
output:
1424404866836930268 37 2 3 7 8 9 10 11 15 16 17 18 19 24 25 26 27 28 30 31 32 33 34 35 36 37 38 40 41 43 44 45 46 48 51 53 55 56
result:
ok n=100000
Test #17:
score: 0
Accepted
time: 896ms
memory: 5176kb
input:
100000 843150893847780301 1181820508008317 340701418258404238 947868317231577274 770147842713796842 916714701940076930 800452952253252740 104881620878724987 266972439028287070 241688123576208108 596705197498862941 562457415255691769 703244077935150731 957002837169210764 102033601647984887 3320392305...
output:
1789402858688069306 31 1 2 4 5 7 8 9 11 16 19 20 25 27 29 31 32 33 34 35 37 40 42 43 46 48 49 53 54 56 58 59
result:
ok n=100000
Test #18:
score: 0
Accepted
time: 906ms
memory: 5124kb
input:
100000 843977132730896429 437410780376524459 80636129997408989 955980523257206750 355557531693146099 710318858924747201 687960160277992015 519713328221908975 639668804954253931 280122255563544994 469421312173123382 546035614312218811 343208235167918118 723221904048813000 75210151574987910 1209212026...
output:
1329681042070227517 34 2 3 4 5 8 9 10 12 16 17 18 19 21 22 24 26 27 29 30 31 37 39 40 41 43 44 46 47 48 49 50 52 56 62
result:
ok n=100000
Test #19:
score: 0
Accepted
time: 904ms
memory: 5348kb
input:
100000 844803375908979853 873639731655106010 43942878591189538 964092724987868930 940967220672495357 727295048469225974 352095322858020900 934545035565092963 12365175175188086 318556391845849176 342137431142351118 529613809073778556 266068938368606734 909803174729513631 577298171346544271 2372614560...
output:
1884838755472958218 24 1 2 3 13 14 16 17 20 21 22 23 24 26 30 33 42 43 44 45 46 47 49 50 51
result:
ok n=100000