oj.uz

답안 #518276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518276 2022-01-23T10:07:53 Z Be_dos XOR Sum (info1cup17_xorsum) C++17
0 / 100
 1600 ms 96752 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_more(max_allowed + 1);
                if(num_less % 2 == 1)
                    ans ^= 1 << j;
            }
        }
    }
    std::cout << ans;
    return 0;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 7532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1629 ms 96752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1629 ms 96752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 7532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 7532 KB Output isn't correct
2 Halted 0 ms 0 KB -