oj.uz

Submission #1018308

# Submission time Handle Problem Language Result Execution time Memory
1018308 2024-07-09T18:46:05 Z KindaNameless XOR Sum (info1cup17_xorsum) C++14
100 / 100
 597 ms 35108 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

const int LIM = 1000000;

int V[LIM + 1];
pair<int, int> helper[LIM + 1], A[LIM + 1], B[LIM + 1];
int N;

int cnt(int X){
    int l = 0, r = N - 1;
    int res = 0;
    for(int i = 0; i < N; ++i){
        if(2 * helper[i].first <= X){
            res++;
        }
    }
    while(l < r){
        if(helper[l].first + helper[r].first <= X){
            res += r - l;
            l++;
        }
        else{
            r--;
        }
    }
    return res;
}

int calc(int L, int R){
    return cnt(R) - cnt(L - 1);
}

void solve(){
    cin >> N;

    for(int i = 0; i < N; ++i){
        cin >> V[i];
        helper[i] = {V[i] & 1, i};
    }

    sort(helper, helper + N);

    int answer = 0;
    for(int j = 0; j < 30; ++j){
        if(j > 0){
            int p1 = -1, p2 = -1;
            for(int i = 0; i < N; ++i){
                if(!(V[helper[i].second] >> j & 1)){
                    A[++p1] = {helper[i].first, helper[i].second};
                }
                else{
                    B[++p2] = {helper[i].first + (1 << j), helper[i].second};
                }
            }
            for(int i = 0; i <= p1; ++i){
                helper[i] = A[i];
            }
            for(int i = 0; i <= p2; ++i){
                helper[i + p1 + 1] = B[i];
            }
        }
        int total = calc((1 << j), (1 << (j + 1)) - 1) + calc((1 << (j + 1)) + (1 << j), (1 << (j + 2)) - 1);
        if(total & 1)answer += (1 << j);
    }

    cout << answer << "\n";
}

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

    int tc = 1; //cin >> tc;

    while(tc--){
        solve();
    }

    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 30292 KB Output is correct
2 Correct 363 ms 29612 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 30292 KB Output is correct
2 Correct 363 ms 29612 KB Output is correct
3 Correct 461 ms 32308 KB Output is correct
4 Correct 442 ms 32132 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 62 ms 11564 KB Output is correct
4 Correct 61 ms 11600 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 392 ms 30292 KB Output is correct
4 Correct 363 ms 29612 KB Output is correct
5 Correct 461 ms 32308 KB Output is correct
6 Correct 442 ms 32132 KB Output is correct
7 Correct 62 ms 11564 KB Output is correct
8 Correct 61 ms 11600 KB Output is correct
9 Correct 597 ms 35108 KB Output is correct
10 Correct 517 ms 35108 KB Output is correct
11 Correct 580 ms 35004 KB Output is correct