Submission #1140909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140909		__Davit__	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	854 ms	34180 KiB

xorsum

#include<bits/stdc++.h>

#define ll long long
#define lld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vr(v) v.begin(),v.end()
#define rv(v) v.rbegin(),v.rend()


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag,
    tree_order_statistics_node_update> ordered_set;


//#include "algo/debug.h"


void solve() {
    int n;
    cin >> n;
    vector<ll> v(n);
    ll answer = 0;
    for (int i = 0; i < n; i++)cin >> v[i];
    vector<ll> a;

    auto f = [&](ll x)-> ll {
        //the number of pairs whose sum does not exceed x
        ll res = 0;
        int it = n - 1;
        for (int i = 0; i < n; i++) {
            while (it >= i && a[i] + a[it] > x) {
                it--;
            }
            if (it < i)break;
            res += it - i + 1;
        }
        return res;
    };


    for (int i = 0; i < 31; i++) {
        //radix sort
        vector<ll> zro, mek;
        for (int j = 0; j < n; j++) {
            if ((v[j] >> i) & 1)mek.pb(v[j]);
            else zro.pb(v[j]);
        }
        v.clear();
        for (int j = 0; j < (int) zro.size(); j++)v.pb(zro[j]);
        for (int j = 0; j < (int) mek.size(); j++)v.pb(mek[j]);
        a.clear();

        // for (int j = 0; j < n; j++)a.pb(v[j] % (1ll << (i + 1)));
        for (int j = 0; j < n; j++)a.pb(v[j] & ((1ll << (i + 1)) - 1));
        ll val = f((1ll << (i + 1)) - 1) - f((1ll << (i)) - 1);
        val += f((1ll << (i + 2)) - 2) - f((1ll << (i + 1)) + (1ll << (i)) - 1);

        if (val & 1)answer += (1ll << i);
    }
    cout << answer << endl;
}

int main() {
    int t = 1;
    // cin >> t;
    while (t--)solve();
}

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