QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#468855#1899. Maximaze XOR sumnhtd211008WA 0ms3824kbC++201.5kb2024-07-09 02:01:202024-07-09 02:01:20

Judging History

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

  • [2024-07-09 02:01:20]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3824kb
  • [2024-07-09 02:01:20]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define bit(x,i) (x>>i&1)
#define merge(res,a,b) set_symmetric_difference(a.begin(),a.end(),b.begin(),b.end(),back_inserter(res));
struct xor_basis{
    int basis[60]={0};
    vector<int> trace[60];
    xor_basis(){};
    int cnt=0;
    void insert(int x,vector<int>& a){
        for(int i=59;i>=0;i--)if(bit(x,i)){
            if(basis[i]){
                x^=basis[i];
                merge(a,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,A=0,B=0;
    cin>>n;
    int 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];
        vector<int> v={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];
            merge(res,res,sus.trace[i]);
        }
        else{
            int 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: 3624kb

input:

2
1 1
2 2

output:

6 1
1 

result:

ok n=2

Test #2:

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

input:

3
2 1 4
4 0 4

output:

7 0

result:

ok n=3

Test #3:

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

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

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: -100
Wrong Answer
time: 0ms
memory: 3516kb

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 7
3 2 0 1 3 94761079537680 0 

result:

wrong answer Integer 0 violates the range [1, 100]