Submission #889393

#	Time	Username	Problem	Language	Result	Execution time	Memory
889393		boris_mihov	XOR Sum (info1cup17_xorsum)	C++17	0 / 100	1636 ms	23888 KiB

xorsum

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXLOG = 31;

int n;
int cnt[2];
llong a[MAXN];
llong b[MAXN];
llong c[MAXN];
llong answer;

void solve()
{
    for (int bit = 0 ; bit < MAXLOG ; ++bit)
    {
        int cntOnes = 0;
        std::iota(c + 1, c + 1 + n, 1);
        std::sort(c + 1, c + 1 + n, [&](int x, int y)
        {
            return b[x] < b[y];
        });

        int ptr = n + 1;
        llong count = 1LL * cntOnes * (n - cntOnes);
        for (int i = 1 ; i <= n ; ++i)
        {
            while (ptr > 1 && b[c[ptr - 1]] + b[c[i]] >= (1 << bit))
            {
                ptr--;
            }

            count += n + 1 - ptr;
        }

        if (count & 1)
        {
            answer |= (1 << bit);
        }
    
        for (int i = 1 ; i <= n ; ++i)
        {
            b[i] |= (a[i] & (1 << bit));
            cntOnes += ((a[i] & (1 << bit)) > 0);
        }
    }

    std::cout << answer << '\n';
}

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

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}  

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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