QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59390 | #4810. Add One | captured# | WA | 2ms | 3636kb | C++14 | 1.6kb | 2022-10-29 15:02:49 | 2022-10-29 15:02:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define LL long long
#define deb(x) cerr<<#x<<" "<<x<<" "
#define dnl cerr<<endl
const int maxn = 1e6+5;
LL arr[maxn];
const int d=64;
LL basis[d];
int sz;
void insertVector(LL mask)
{
for(int i=0; i<d; i++)
{
if((mask&(1LL<<i))==0)
continue;
if(!basis[i])
{
basis[i]=mask;
++sz;
return;
}
mask^=basis[i];
}
}
LL possible(int k){
LL ans = 0;
for(int i=0;i<k;i++){
// if((ans&(1LL<<i))>0)continue;
if( !basis[i] )return 0;
ans ^= basis[i];
}
LL big = 1LL<<(k);
if((big&ans) > 0){
// return 0;
if(!basis[k])return 0;
ans ^= basis[k];
}
for(int i=0;i<k;i++){
if(((1LL<<i)&ans) > 0)continue;
return 0;
}
return 1;
}
void solve(int cs){
int n;
cin>>n;
LL x = 0;
for(int i=1;i<=n;i++){
cin>>arr[i];
x ^= arr[i];
insertVector(arr[i]);
}
// deb(x);dnl;
const int dsz = 60;
LL ans = x;
// for(int i=0;i<dsz;i++){
// deb(i);deb(basis[i]);dnl;
// }
for(int i=1;i<=dsz;i++){
LL a = possible(i);
if(a==0)continue;
LL cur = x;
// cur ^= a;
// LL newval = a+1;
// cur ^= newval;
LL di = 1LL<<(i+1);
di--;
ans = max(ans,cur^di);
}
cout<<ans<<endl;
}
int main(){
int t;t = 1;
// cin>>t;
for(int cs=1;cs<=t;cs++)solve(cs);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3636kb
input:
4 1 2 1 2
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
5 1 2 3 4 5
output:
14
result:
ok 1 number(s): "14"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3588kb
input:
6 1 2 4 7 15 31
output:
47
result:
ok 1 number(s): "47"
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 3496kb
input:
5 41 40 50 11 36
output:
31
result:
wrong answer 1st numbers differ - expected: '99', found: '31'