Submission #518280

#	Time	Username	Problem	Language	Result	Execution time	Memory
518280		Be_dos	XOR Sum (info1cup17_xorsum)	C++17	7 / 100	1701 ms	97468 KiB

xorsum

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T,
                        null_type,
                        std::less<T>,
                        rb_tree_tag,
                        tree_order_statistics_node_update>;

struct Tracker {
    ordered_set<std::pair<int32_t, int32_t> > set;

    int32_t cnt = 0;
    void add(int32_t x) {
        set.insert({x, cnt++});
    }

    int32_t get_less(int32_t x) {
        return set.order_of_key({x, -1});
    }

    int32_t get_more(int32_t x) {
        return set.size() - set.order_of_key({x + 1, -1});
    }
};
     
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int32_t n;
    std::cin >> n;

    int32_t* arr = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];

    std::pair<Tracker, Tracker>* trackers = new std::pair<Tracker, Tracker>[29];
    int32_t ans = 0;
    for(int32_t i = 0; i < n; i++) {
        for(int32_t j = 0; j < 29; j++) {
            int32_t my_suffix = arr[i] & ((1 << j) - 1);
            if(arr[i] & (1 << j)) {
                trackers[j].second.add(my_suffix);

                int32_t max_allowed = (1 << j) - my_suffix - 1;
                int32_t num_less = trackers[j].first.get_less(max_allowed + 1);
                if(num_less % 2 == 1)
                    ans ^= 1 << j;

                int32_t min_allowed = (1 << j) - my_suffix;
                int32_t num_more = trackers[j].second.get_more(min_allowed - 1);
                if(num_more % 2 == 1)
                    ans ^= 1 << j;
            } else {
                trackers[j].first.add(my_suffix);

                int32_t min_allowed = (1 << j) - my_suffix;
                int32_t num_more = trackers[j].first.get_more(min_allowed - 1);
                if(num_more % 2 == 1)
                    ans ^= 1 << j;

                int32_t max_allowed = (1 << j) - my_suffix - 1;
                int32_t num_less = trackers[j].second.get_less(max_allowed + 1);
                if(num_less % 2 == 1)
                    ans ^= 1 << j;
            }
        }
    }
    std::cout << ans << "\n";

    /*int32_t ans2 = 0;
    for(int32_t i = 0; i < n; i++)
        for(int32_t j = i; j < n; j++)
            ans2 ^= arr[i] + arr[j];
    std::cout << ans2;*/
    return 0;
}
     

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23