Codeforces Round #626 (Div. 1) B. Present (R2100)

確かに AtCoder で完全既出だった！

drken1215.hatenablog.com

問題へのリンク

問題概要

要素の数列 が与えられる。これらから 2 つ選んで和をとって得られる 個の整数の XOR 和を求めよ。

制約

• 
• 

#include <bits/stdc++.h>
using namespace std;

const int INF = 1<<30;
int MAX_DIGIT = 25;
int N;
vector<int> a;

int solve() {
    long long res = 0;
    for (int d = MAX_DIGIT-1; d >= 0; --d) {
        sort(a.begin(), a.end());
        vector<int> zero, one;
        for (int i = 0; i < N; ++i) {
            if (a[i] & (1<<d)) one.push_back(a[i] - (1<<d));
            else zero.push_back(a[i]);
        }
        long long num = 0;
        for (int i = 0; i < zero.size(); ++i) {
            int id = lower_bound(zero.begin(), zero.end(), (1<<d)-zero[i]) - zero.begin();
            chmax(id, i+1);
            num += N - id;

            id = lower_bound(one.begin(), one.end(), (1<<d)-zero[i]) - one.begin();
            num += id;
        }
        for (int i = 0; i < one.size(); ++i) {
            int id = lower_bound(one.begin(), one.end(), (1<<d)-one[i]) - one.begin();
            chmax(id, i+1);
            num += N - id;
        }
        if (num % 2 == 1) res += (1<<d);
        for (int i = 0; i < N; ++i) {
            if (a[i] & (1<<d)) a[i] -= (1<<d);
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> N) {
        a.resize(N);
        for (int i = 0; i < N; ++i) cin >> a[i];
        cout << solve() << endl;
    }
}