oj.uz

Submission #660866

# Submission time Handle Problem Language Result Execution time Memory
660866 2022-11-23T11:05:26 Z Bagritsevich_Stepan XOR Sum (info1cup17_xorsum) C++14
100 / 100
 730 ms 31132 KB 
#include <iostream>

using namespace std;

const int maxN = 1e6 + 5;

pair<int, int> sortArray[2][maxN];
pair<int, int> x[maxN];
int a[maxN];

bool GetBit(const int x, const int k) {
    return x & (1 << k);
}

void Sort(const int bit, const int n) {
    for (int i = 0; i < n; i++) {
        if (GetBit(a[x[i].second], bit)) {
            x[i].first |= 1 << bit;
        }
    }

    int size[] = {0, 0};
    for (int i = 0; i < n; i++) {
        int index = GetBit(x[i].first, bit);
        sortArray[index][size[index]++] = x[i];
    }

    int index = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < size[i]; j++) {
            x[index++] = sortArray[i][j];
        }
    }
}

void UpdateP(int& p, const int i, const int value) {
    p = max(p, i);
    while (i < p && x[i].first + x[p - 1].first >= value) {
        p--;
    }
}

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

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        x[i].second = i;
    }

    int result = 0;
    for (int bit = 0; bit < 30; bit++) {
        Sort(bit, n);

        int p1 = n;
        int p2 = n;
        int p3 = n;
        const int value = 1 << bit;

        for (int i = 0; i < n; i++) {
            UpdateP(p1, i, value);
            UpdateP(p2, i, 2 * value);
            UpdateP(p3, i, 3 * value);
            if ((p2 - p1 + n - p3) % 2) {
                result ^= value;
            }
        }
    }

    cout << result << '\n';
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 468 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 30296 KB Output is correct
2 Correct 480 ms 28316 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 30296 KB Output is correct
2 Correct 480 ms 28316 KB Output is correct
3 Correct 586 ms 31116 KB Output is correct
4 Correct 568 ms 30332 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 73 ms 3792 KB Output is correct
4 Correct 71 ms 3792 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 519 ms 30296 KB Output is correct
4 Correct 480 ms 28316 KB Output is correct
5 Correct 586 ms 31116 KB Output is correct
6 Correct 568 ms 30332 KB Output is correct
7 Correct 73 ms 3792 KB Output is correct
8 Correct 71 ms 3792 KB Output is correct
9 Correct 730 ms 31132 KB Output is correct
10 Correct 728 ms 31016 KB Output is correct
11 Correct 713 ms 31080 KB Output is correct