Submission #1293196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293196		WonderfulWhale	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	680 ms	13372 KiB

xorsum

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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin >> v[i];
    int ans = 0;
    for(int bit=0;bit<30;bit++) {
        vector<int> zero, one;
        int l=0, r=-1;
        for(int x:v) {
            int mask = (1<<(bit+1))-1;
            int y = x & ((1<<bit)-1);
            pair<int, int> range = {(1<<bit) - y, (1<<(bit+1)) - y - 1};
            if(x & (1<<bit)) {
                one.push_back(x);
                if(r == one.size()-2)
                    r++;
            } else {
                zero.push_back(x);
                if(l == zero.size()-1)
                    l++;
            }
            while(l>0 && (zero[l-1]&mask)>=range.first)
                l--;
            while(r!=-1 && (one[r]&mask)>range.second)
                r--;
            int valid = (zero.size() - l) + (r + 1);
            int cnt = (x & (1<<bit)) ? (zero.size()+one.size()) - valid : valid;
            if(cnt % 2)
                ans ^= 1 << bit;
        }
        v = zero;
        v.insert(v.end(), one.begin(), one.end());
    }
    cout << ans << "\n";
}

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