oj.uz

Submission #413486

# Submission time Handle Problem Language Result Execution time Memory
413486 2021-05-28T19:18:58 Z KKT89 XOR Sum (info1cup17_xorsum) C++17
100 / 100
 827 ms 25848 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

const int MAXN=1e6+5;
pair<int,int> x[MAXN];
pair<int,int> for_sort[2][MAXN];
int sz[2];

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
        x[i]={0,i};
    }
    int res=0;
    for(int bit=0;bit<30;bit++){
        auto Sort=[&](int bit)->void{
            sz[0]=sz[1]=0;
            for(int i=0;i<n;i++){
                if((1<<bit)&a[x[i].second]){
                    x[i].first|=(1<<bit);
                    for_sort[1][sz[1]++]=x[i];
                }
                else{
                    for_sort[0][sz[0]++]=x[i];
                }
            }
            int id=0;
            for(int i=0;i<2;i++){
                for(int j=0;j<sz[i];j++){
                    x[id++]=for_sort[i][j];
                }
            }
        };
        Sort(bit);
        int t=0;
        int v=(1<<bit);
        for(int i=n-1,j=0,k=0,l=0;i>=0;i--){
            j=min(j,i); k=min(k,i); l=min(l,i);
            while(j<i+1 and x[i].first+x[j].first<v)j++;
            while(k<i+1 and x[i].first+x[k].first<2*v)k++;
            while(l<i+1 and x[i].first+x[l].first<3*v)l++;
            t+=(k-j)+(n-l);
            t&=1;
        }
        if(t)res^=v;
    }
    cout << res << endl;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 25828 KB Output is correct
2 Correct 570 ms 24156 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 25828 KB Output is correct
2 Correct 570 ms 24156 KB Output is correct
3 Correct 681 ms 25760 KB Output is correct
4 Correct 661 ms 24852 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 76 ms 2764 KB Output is correct
4 Correct 75 ms 2852 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 617 ms 25828 KB Output is correct
4 Correct 570 ms 24156 KB Output is correct
5 Correct 681 ms 25760 KB Output is correct
6 Correct 661 ms 24852 KB Output is correct
7 Correct 76 ms 2764 KB Output is correct
8 Correct 75 ms 2852 KB Output is correct
9 Correct 827 ms 25648 KB Output is correct
10 Correct 804 ms 25848 KB Output is correct
11 Correct 793 ms 25796 KB Output is correct