Submission #1018308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018308		KindaNameless	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	597 ms	35108 KiB

xorsum

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

const int LIM = 1000000;

int V[LIM + 1];
pair<int, int> helper[LIM + 1], A[LIM + 1], B[LIM + 1];
int N;

int cnt(int X){
    int l = 0, r = N - 1;
    int res = 0;
    for(int i = 0; i < N; ++i){
        if(2 * helper[i].first <= X){
            res++;
        }
    }
    while(l < r){
        if(helper[l].first + helper[r].first <= X){
            res += r - l;
            l++;
        }
        else{
            r--;
        }
    }
    return res;
}

int calc(int L, int R){
    return cnt(R) - cnt(L - 1);
}

void solve(){
    cin >> N;

    for(int i = 0; i < N; ++i){
        cin >> V[i];
        helper[i] = {V[i] & 1, i};
    }

    sort(helper, helper + N);

    int answer = 0;
    for(int j = 0; j < 30; ++j){
        if(j > 0){
            int p1 = -1, p2 = -1;
            for(int i = 0; i < N; ++i){
                if(!(V[helper[i].second] >> j & 1)){
                    A[++p1] = {helper[i].first, helper[i].second};
                }
                else{
                    B[++p2] = {helper[i].first + (1 << j), helper[i].second};
                }
            }
            for(int i = 0; i <= p1; ++i){
                helper[i] = A[i];
            }
            for(int i = 0; i <= p2; ++i){
                helper[i + p1 + 1] = B[i];
            }
        }
        int total = calc((1 << j), (1 << (j + 1)) - 1) + calc((1 << (j + 1)) + (1 << j), (1 << (j + 2)) - 1);
        if(total & 1)answer += (1 << j);
    }

    cout << answer << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1; //cin >> tc;

    while(tc--){
        solve();
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23