QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468894#1899. Maximaze XOR sumnhtd211008TL 558ms3868kbC++231.7kb2024-07-09 02:31:382024-07-09 02:31:38

Judging History

你现在查看的是最新测评结果

  • [2024-07-09 02:31:38]
  • 评测
  • 测评结果:TL
  • 用时:558ms
  • 内存:3868kb
  • [2024-07-09 02:31:38]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#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(NULL);
    cout.tie(NULL);
    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<<" ";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3868kb

input:

2
1 1
2 2

output:

6 1
1 

result:

ok n=2

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3
2 1 4
4 0 4

output:

7 0

result:

ok n=3

Test #3:

score: 0
Accepted
time: 0ms
memory: 3616kb

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: 3828kb

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: 3512kb

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: 3572kb

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: 0ms
memory: 3668kb

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: 3584kb

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: 3596kb

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: 3680kb

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: 3792kb

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: 558ms
memory: 3824kb

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...

output:


result: