QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#468889 | #1899. Maximaze XOR sum | nhtd211008 | TL | 552ms | 3784kb | C++23 | 1.8kb | 2024-07-09 02:27:14 | 2024-07-09 02:27:15 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
// #define int long long
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];
xor_basis(){};
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;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
long long A=0,B=0;
cin>>n;
long long a[n+1],b[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
A^=a[i];
}
vector<int> v;
for(int i=1;i<=n;i++){
cin>>b[i];
B^=b[i];
v.push_back(i);
sus.insert(a[i]^b[i],v);
}
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> a=sus.trace[i];
sus.basis[i]=0;
sus.trace[i].clear();
sus.insert(x,a);
}
}
cout<<A+B<<" "<<res.size()<<'\n';
for(int i:res) cout<<i<<" ";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 2 1 4 4 0 4
output:
7 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3784kb
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: 3780kb
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: 3532kb
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: 1ms
memory: 3540kb
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: 3564kb
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: 2ms
memory: 3580kb
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: 3ms
memory: 3516kb
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 6 1 2 5 6 7 9
result:
ok n=1000
Test #10:
score: 0
Accepted
time: 5ms
memory: 3596kb
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: 118ms
memory: 3660kb
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: 552ms
memory: 3784kb
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 21 1 3 4 5 7 9 12 17 18 23 24 25 28 29 30 31 32 34 36 41 42
result:
ok n=7890
Test #13:
score: -100
Time Limit Exceeded
input:
10000 1024699458171845 273191988760302 672954995688326 856568833018077 965082229777704 277750079399023 667877391291263 435567952575490 586753361866430 328361268020042 1013607754170263 601702869301405 1104383095207561 1094567873246657 910010660363394 921121581843645 908188549630208 527368341706711 95...