563.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <stdint.h>
#include <vector>
#include <algorithm>

// Функция, возвращающая бит числа num в разряде pos
inline int bit(int num, int pos) {
    return num & (1LL << pos);
}

// Рекурсивная поразрядная сортировка вектора:
void bits_sort(std::vector<int>& v, int begin, int end, int level) {
    if (begin == end || level == 32) return;
    int len0, len1;
    {
        std::vector<int> equal0, equal1; // Две части массива: содержащие 0 и содержащие 1 в текущем разряде

        for (int i = begin; i <= end; ++i) {
            if (bit(v[i], level) == 0) {
                equal0.push_back(v[i]);
            } else {
                equal1.push_back(v[i]);
            }
        }

        len0 = (int)equal0.size();
        len1 = (int)equal1.size();

        int i = begin;
        for (int j = 0; j < len0; v[i++] = equal0[j++]);
        for (int j = 0; j < len1; v[i++] = equal1[j++]);
    }
    // Рекурсивные вызовы от обоих частей:
    if (len0 > 1) bits_sort(v,      begin, begin+len0-1, level+1);
    if (len1 > 1) bits_sort(v, begin+len0,          end, level+1);
}

// Решение задачи:
int solve(std::vector<int> arr) {
    // Вычисляем XOR от всех чисел массива arr:
    int s = 0; for (auto it : arr) s ^= it;

    // Применяем побитовую сортировку:
    bits_sort(arr, 0, (int)arr.size()-1, 0);

    // Основной цикл по числам:
    for (int i = 0; i < (int)arr.size()-1; ++i) {
        int low = i+1, high = (int)arr.size()-1;
        // Цикл по разрядам:
        for (int pos = 0; high >= low && pos < 32; ++pos) {
            // Разобьем оставшуюся часть массива на две группы:
            // [low,  mid) - разряд на позиции pos совпадает с соответствующим разрядом числа a[i]
            // [mid, high] - разряд на позиции pos не совпадает с соответствующим разрядом числа a[i]

            // Находим mid бинпоиском:
            int mid;
            if (bit(arr[i], pos) == bit(arr[low], pos)) {
                if (bit(arr[i], pos) != bit(arr[high], pos)) {
                    int l = low, h = high;
                    while (h - l > 1) {
                        int m = (l + h) / 2;
                        if (bit(arr[i], pos) == bit(arr[m], pos)) {
                            l = m;
                        } else {
                            h = m;
                        }
                    }
                    mid = h;
                } else {
                    mid = high + 1;
                }
            } else {
                mid = low;
            }
            // Результат:
            // бит совпадает для всех чисел от [low, mid)
            // high-mid+1 чисел имеют общий префикс длиной pos
            if ((high-mid+1) % 2 == 1) { // Обновляем результат:
                s ^= (1 << pos) - 1;
            }
            high = mid-1; // спуск к тем числам, разряд у которых совпал
        }
        if (high >= low && (high-low+1) % 2 == 1) { // Обрабатываем последнюю группу - группу чисел с максимальным префиксом = 32:
            s ^= -1;
        }
    }
    return s;
}

int main() {
    freopen("input.txt", "rt", stdin);
    int n; scanf("%d", &n);
    std::vector<int> a(n); for (auto & it : a) scanf("%d", &it);
    printf("%d", solve(a));

    return 0;
}