QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#59386#4810. Add Onecaptured#WA 2ms3588kbC++141.5kb2022-10-29 14:56:142022-10-29 14:56:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-29 14:56:17]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3588kb
  • [2022-10-29 14:56:14]
  • 提交

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] )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 ans;
}


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;
        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: 3560kb

input:

4
1 2 1 2

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 2ms
memory: 3588kb

input:

5
1 2 3 4 5

output:

14

result:

ok 1 number(s): "14"

Test #3:

score: 0
Accepted
time: 2ms
memory: 3504kb

input:

6
1 2 4 7 15 31

output:

47

result:

ok 1 number(s): "47"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3472kb

input:

5
41 40 50 11 36

output:

31

result:

wrong answer 1st numbers differ - expected: '99', found: '31'