Submission #749024

#	Time	Username	Problem	Language	Result	Execution time	Memory
749024		LucaLucaM	XOR Sum (info1cup17_xorsum)	C++17	0 / 100	185 ms	8832 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e6;

int a[NMAX + 5];

/**
cate perechi (i, j) exista astfel incat
a[i] + a[j] au bitul B setat
(1 << bt) <= a[i] + a[j] < (1 << (bt + 1))
**/

int n;

bool solve (int bt)
{
    bool ans = 0;
    for (int i=1, j=n; i<=n; i++)
    {
        j = (j < i? i : j);
        while (j >= i && a[i] + a[j] >= (1 << bt))
            j--;
        ans ^= (n - j) & 1;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

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

    sort(a+1, a+n+1);

    bool prv = 0;
    int ans = 0;

    for (int bt=29; bt>=0; bt--)
    {
        bool cur = solve(bt);
        if (cur != prv)
            {
                ans |= (1 << bt);
                prv = cur;
            }
    }

    cout << ans;

    return 0;
}

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