Submission #197188

#	Time	Username	Problem	Language	Result	Execution time	Memory
197188		Pankin	XOR Sum (info1cup17_xorsum)	C++14	45 / 100	1634 ms	16120 KiB

xorsum

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>

const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;
using namespace __gnu_pbds;

bool valid(int x, int y, int n, int m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

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

const int N = 1000000 + 5;
int order[N], p[N][2], o[2], a[N], n, ans = 0;

signed main() {
    fast_io;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        order[i] = i;
    }

    int curmask = 0;
    for (int bit = 0; bit < 29; bit++) {
        o[0] = o[1] = 0;

        for (int i = 0; i < n; i++) {
            p[o[(a[order[i]]>>bit)&1]][(a[order[i]]>>bit)&1] = order[i];
            o[(a[order[i]]>>bit)&1]++;
        }

        int pointer[2] = {o[0], o[1]}, same = 0, col = 0;
        for (int i = 0; i < n; i++) {
            for (int bt = 0; bt < 2; bt++) {
                while(pointer[bt] > 0 && (a[p[pointer[bt] - 1][bt]]&curmask) + (a[order[i]]&curmask) >= (1 << bit))
                    pointer[bt]--;

                if (((a[order[i]]>>bit)&1) != bt)
                    col += pointer[bt];
                else
                    col += o[bt] - pointer[bt];
            }

            if (((a[order[i]] + a[order[i]])>>bit)&1)
                same++;
            same &= 3;
            col  &= 3;
        }
        col = col + 4 - same;
        col &= 3;
        col >>= 1;
        col += same;

        ans |= ((col&1) << bit);

        int cur = 0;
        for (int bt = 0; bt < 2; bt++) {
            for (int i = 0; i < o[bt]; i++) {
                order[cur] = p[i][bt];
                cur++;
            }
        }

        curmask <<= 1;
        curmask++;
    }

    cout << ans;

    return 0;
}

/*
2
7 0
*/

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