QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#468903#1899. Maximaze XOR sumnhtd211008AC ✓915ms5196kbC++231.7kb2024-07-09 02:39:042024-07-09 02:39:05

Judging History

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

  • [2024-07-09 02:39:05]
  • 评测
  • 测评结果:AC
  • 用时:915ms
  • 内存:5196kb
  • [2024-07-09 02:39:04]
  • 提交

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];
    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];
    }
    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: 3536kb

input:

2
1 1
2 2

output:

6 1
1 

result:

ok n=2

Test #2:

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

input:

3
2 1 4
4 0 4

output:

7 0

result:

ok n=3

Test #3:

score: 0
Accepted
time: 1ms
memory: 3604kb

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: 1ms
memory: 3848kb

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: 1ms
memory: 3540kb

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

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

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: 1ms
memory: 3840kb

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

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

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

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

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

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: 483ms
memory: 4400kb

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: 904ms
memory: 5108kb

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: 902ms
memory: 5108kb

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: 897ms
memory: 5196kb

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: 913ms
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: 915ms
memory: 5012kb

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