Submission #1122259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122259		I_love_Banu	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	867 ms	17620 KiB

xorsum

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

using ll = long long;

#define FOR(i, a) for(int i=0;i<(a);i++)
#define FORd(i, a) for(int i=(a)-1;0<=i;i--)

const int mxN = 1000006;

int v[mxN];
int v1[mxN];
int N, x;

void sor() {
    int co = 0;
    FOR(i, N) {
        if (~v[i] & x) {
            co ++;
        }
    }
    int co0 = 0;
    FOR(i, N) {
        if (~v[i] & x) {
            v1[co0 ++] = v[i];
        } else {
            v1[co ++] = v[i];
        }
    }
    swap(v, v1);
}

int get(int ix) {
    int bias = 0;
    if (ix < 0) {
        bias -= 2 * x;
        ix += N;
    } else if (ix >= N) {
        bias += 2 * x;
        ix -= N;
    }
    return (v[ix] & (2 * x - 1)) + bias;
}

ll solv(int f = 0) {
    sor();
    ll ans = 0;
    FOR(i, N) {
        if ((2 * v[i]) & x) {
            ans ++;
        }
    }
    int j = -N, k = -N;
    FORd(i, N) {
        int e = v[i] & (2 * x - 1);
        while (get(j) < x - e) {
            j ++;
        }
        while (get(k) < 2 * x - e) {
            k ++;
        }
        ans += k - j;
    }
    return ans / 2;
}

main() {
    cin >> N;

    FOR(i, N) {
        cin >> v[i];
    }

    int ans = 0;
    FOR(i, 30) {
        x = 1 << i;
        if (solv() & 1) {
            ans += x;
        }
    }

    cout << ans << endl;
}

Compilation message (stderr)

xorsum.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main() {
      | ^~~~

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