제출 #413486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413486		KKT89	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	827 ms	25848 KiB

xorsum

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23