QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#468878 | #1899. Maximaze XOR sum | nhtd211008 | WA | 1ms | 3632kb | C++20 | 1.7kb | 2024-07-09 02:17:50 | 2024-07-09 02:17:50 |
Judging History
answer
#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{
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];
a=merge(a,trace[i]);
}
else{
cnt++;
basis[i]=x;
trace[i].swap(a);
return;
}
}
}
} sus;
const int maxn=1e5+1;
int n,A=0,B=0;
int a[maxn],b[maxn];
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];
}
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{
int 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<<" ";
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3560kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
3 2 1 4 4 0 4
output:
7 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
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: 3604kb
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: 3632kb
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 2 1 3
result:
wrong answer Wrong sum