Submission #389302

#	Time	Username	Problem	Language	Result	Execution time	Memory
389302		balbit	XOR Sum (info1cup17_xorsum)	C++14	45 / 100	1672 ms	12396 KiB

xorsum

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
//#ifndef BALBIT
//#include "grader.h"
//#endif

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBITs

int re = 0;
//
//vector<int> y1, y0;

void go(vector<int> &v, int bit) {
    vector<int> y1, y0;
    for (int &x : v) {
        if (x & (1<<bit)) {
            x ^= (1<<bit);
            y1.pb(x);
        }else{
            y0.pb(x);
        }
    }
    sort(ALL(y1)); sort(ALL(y0));
//    if ((SZ(y1)*(ll)(SZ(y1)+1)/2) & 1) re^=(1<<(bit+1));
    if (bit == 0) {
        if ((SZ(y1)&1) && (SZ(y0)&1)) {
            re ^= 1;
        }
        return;
    }
    if (SZ(y1) && SZ(y0)) {
        bool over = 0;
        int j = SZ(y0);
        REP(i, SZ(y1)) {
            while (j-1>=0 && y0[j-1] + y1[i] >= (1<<bit)) {
                --j;
            }
            over ^= (SZ(y0) - j)&1;
        }
//        if (over) re ^= (1<<(bit+1));
        if (((SZ(y0) * (ll)(SZ(y1))) ^ over)&1) {
            re ^= 1<<bit;
        }
    }
    if (SZ(y1)) {
        int j = SZ(y1);
        bool over = 0;
        REP(i, SZ(y1)) {
            while (j-1 >= i && y1[j-1] + y1[i] >= (1<<bit)) --j;
            if (i > j) j=i;
            over ^= (SZ(y1) - j) &1;
        }
        if (over) re ^= (1<<bit);
    }
    if (SZ(y0)) {
        int j = SZ(y0);
        bool over = 0;
        REP(i, SZ(y0)) {
            while (j-1 >= i && y0[j-1] + y0[i] >= (1<<bit)) --j;
            if (i > j) j =i;
            over ^= (SZ(y0) - j) &1;
        }
        if (over) re ^= (1<<bit);
    }
    //    if (SZ(y1)) go(y1, bit-1);
//    if (SZ(y0)) go(y0, bit-1);
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin>>n;
    vector<int> x(n);
    REP(i,n) cin>>x[i];
    for (int i = 30; i>=0; --i) {
        go(x,i);
    }
    cout<<re<<endl;
}

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