oj.uz

Submission #427526

# Submission time Handle Problem Language Result Execution time Memory
427526 2021-06-14T16:29:53 Z Lam_lai_cuoc_doi XOR Sum (info1cup17_xorsum) C++17
100 / 100
 772 ms 17472 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 8128 KB Output is correct
2 Correct 529 ms 7600 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 8128 KB Output is correct
2 Correct 529 ms 7600 KB Output is correct
3 Correct 655 ms 8124 KB Output is correct
4 Correct 625 ms 14352 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 74 ms 1048 KB Output is correct
4 Correct 78 ms 1100 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 576 ms 8128 KB Output is correct
4 Correct 529 ms 7600 KB Output is correct
5 Correct 655 ms 8124 KB Output is correct
6 Correct 625 ms 14352 KB Output is correct
7 Correct 74 ms 1048 KB Output is correct
8 Correct 78 ms 1100 KB Output is correct
9 Correct 764 ms 17472 KB Output is correct
10 Correct 772 ms 17360 KB Output is correct
11 Correct 742 ms 17472 KB Output is correct