제출 #427526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427526		Lam_lai_cuoc_doi	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	772 ms	17472 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 1e6 + 2;
int n, a[N], y[N];

void Read()
{
    cin >> n;

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

#define bit(i, x) (((x) >> (i)) & 1)
#define Get(y, v) ((y) & ((1 << (v)) - 1))

bool Check(int v)
{
    if (v)
    {
        int x[2] = {0, 0};

        for (int i = 1; i <= n; ++i)
            ++x[bit(v - 1, a[i])];
        x[1] += x[0];

        for (int i = n; i; --i)
            y[x[bit(v - 1, a[i])]--] = a[i];

        for (int i = 1; i <= n; ++i)
            a[i] = y[i];
    }

    bool ans(0);
    int cnt(0), cntno(0);

    //cout << v << ":\n";

    for (int i = 1; i <= n; ++i)
        cntno += bit(v, a[i]); //, cout << a[i] << " ";
    //cout << "\n";

    for (int i = 1, j = n; i <= n; ++i)
    {
        cntno -= bit(v, a[i]);

        while (j >= i && Get(a[j], v) + Get(a[i], v) >= (1 << v))
        {
            cntno -= bit(v, a[j]);
            cnt += bit(v, a[j]);
            --j;
        }

        ans ^= (bit(v, a[i]) ? ((j - i - cntno) & 1) : (cntno & 1)) ^ (bit(v, a[i]) ? (cnt & 1) : ((n - j - cnt) & 1));

        //cout << i << " " << j << ": " << cnt << " " << cntno << " " << ans << " " << (bit(v, a[i]) ? (cntno & 1) : ((j - i - cntno) & 1)) << "\n";

        if (i > j)
        {
            cntno += bit(v, a[j + 1]);
            cnt -= bit(v, a[j + 1]);
            ++j;
        }
    }

    return ans;
}

void Solve()
{
    int ans(0);

    for (int i = 0; i < 30; ++i)
        ans |= Check(i) * (1 << i);

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

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