QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#59369#4810. Add Onecaptured#WA 2ms3652kbC++141.5kb2022-10-29 14:15:562022-10-29 14:15:57

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:15:57]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3652kb
  • [2022-10-29 14:15:56]
  • 提交

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

详细

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'