oj.uz

Submission #427522

# Submission time Handle Problem Language Result Execution time Memory
427522 2021-06-14T16:26:37 Z Lam_lai_cuoc_doi XOR Sum (info1cup17_xorsum) C++17
56 / 100
 1600 ms 10960 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];

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)
{
    sort(a + 1, a + n + 1, [&](const int &x, const int &y)
         { return Get(x, v) < Get(y, v); });

    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 8 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 8828 KB Output is correct
2 Correct 1087 ms 8260 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1079 ms 8828 KB Output is correct
2 Correct 1087 ms 8260 KB Output is correct
3 Execution timed out 1638 ms 10960 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 203 ms 1612 KB Output is correct
4 Correct 200 ms 1612 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 8 ms 332 KB Output is correct
3 Correct 1079 ms 8828 KB Output is correct
4 Correct 1087 ms 8260 KB Output is correct
5 Execution timed out 1638 ms 10960 KB Time limit exceeded
6 Halted 0 ms 0 KB -