QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59369 | #4810. Add One | captured# | WA | 2ms | 3652kb | C++14 | 1.5kb | 2022-10-29 14:15:56 | 2022-10-29 14:15:57 |
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=d-1; i>=0; i--)
{
if((mask&(1LL<<i))==0)
continue;
if(!basis[i])
{
basis[i]=mask;
++sz;
return;
}
mask^=basis[i];
}
}
bool possible(int k){
LL ans = 0;
for(int i=k-1;i>=0;i--){
if(ans&(1LL<<i))continue;
if( !basis[i] )return false;
ans ^= basis[i];
}
LL big = 1LL<<(k);
if(ans&big) ans ^= basis[k];
for(int i=0;i<k;i++){
if((1LL<<i)&ans)continue;
return false;
}
return true;
// if( ans&big )return false;
// return true;
}
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 = 59;
LL ans = x;
// for(int i=0;i<dsz;i++){
// deb(i);deb(basis[i]);dnl;
// }
for(int i=1;i<=dsz;i++){
if(possible(i)){
// deb(i);dnl;
LL y = (1LL<<i);
LL cur = y-1;
ans = max(ans,x^y^cur);
}
}
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: 0ms
memory: 3508kb
input:
4 1 2 1 2
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 2ms
memory: 3652kb
input:
5 1 2 3 4 5
output:
14
result:
ok 1 number(s): "14"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3472kb
input:
6 1 2 4 7 15 31
output:
47
result:
ok 1 number(s): "47"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
5 41 40 50 11 36
output:
99
result:
ok 1 number(s): "99"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
6 10 40 60 2 44 47
output:
96
result:
ok 1 number(s): "96"
Test #6:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
6 46 25 39 47 23 60
output:
107
result:
ok 1 number(s): "107"
Test #7:
score: -100
Wrong Answer
time: 2ms
memory: 3380kb
input:
6 56 90 61 63 56 23
output:
79
result:
wrong answer 1st numbers differ - expected: '112', found: '79'