oj.uz

Submission #518280

# Submission time Handle Problem Language Result Execution time Memory
518280 2022-01-23T10:13:38 Z Be_dos XOR Sum (info1cup17_xorsum) C++17
7 / 100
 1600 ms 97468 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 7488 KB Output is correct
2 Correct 68 ms 7608 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1676 ms 97468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1676 ms 97468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 7488 KB Output is correct
2 Correct 68 ms 7608 KB Output is correct
3 Execution timed out 1701 ms 66196 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 7488 KB Output is correct
2 Correct 68 ms 7608 KB Output is correct
3 Execution timed out 1676 ms 97468 KB Time limit exceeded
4 Halted 0 ms 0 KB -