Submission #1122243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122243		I_love_Banu	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	988 ms	131072 KiB

xorsum

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

using ll = long long;

const int mxN = 1000006;
const int mxBt = 32;

ll vbt[mxBt][mxN];
int cnt[mxBt];
int v[mxN];

main() {
    int N;
    cin >> N;

    for (int i = 0; i < N; i ++) {
        cin >> v[i];
    }

    for (int i = mxBt - 1; 0 <= i; i --) {
        for (int j = 0; j < N; j ++) {
            v[j] &= ~(1ll << (i + 1));
            vbt[i][j] = v[j];
        }
        sort(vbt[i], vbt[i] + N);
    }

    for (int i = 0; i < mxBt; i ++) {
        for (int j =  0; j < N; j ++) {
            ll smallLimit = (1ll << (i + 1)) - 1;
            ll smallStart = (1ll << i);
            auto smallLimitIt = upper_bound(vbt[i], vbt[i] + N, smallLimit - vbt[i][j]);
            auto smallStartIt = lower_bound(vbt[i], vbt[i] + N, smallStart - vbt[i][j]);
            cnt[i] += smallLimitIt - smallStartIt;
            ll bigLimit = (1ll << (i + 2)) - 2;
            ll bigStart = (1ll << i) + (1ll << (i + 1));
            auto bigLimitIt = upper_bound(vbt[i], vbt[i] + N, bigLimit - vbt[i][j]);
            auto bigStartIt = lower_bound(vbt[i], vbt[i] + N, bigStart - vbt[i][j]);
            cnt[i] += bigLimitIt - bigStartIt;
        }
    }

    ll ans = 0;
    for (int i = 0; i < mxBt; i ++) {
        if (cnt[i] & 1) {
            ans += (1ll << i);
        }
    }
    
    cout << ans << endl;
}

Compilation message (stderr)

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

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