QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468888 | #1899. Maximaze XOR sum | nhtd211008 | Compile Error | / | / | C++23 | 1.8kb | 2024-07-09 02:26:51 | 2024-07-09 02:26:52 |
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<<" ";
}
Details
In file included from /usr/include/c++/13/string:43, from /usr/include/c++/13/bitset:52, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52, from answer.code:3: /usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’: /usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch 184 | ~allocator() _GLIBCXX_NOTHROW { } | ^ In file included from /usr/include/c++/13/vector:66, from /usr/include/c++/13/functional:64, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53: /usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here 133 | struct _Vector_impl | ^~~~~~~~~~~~