oj.uz

Submission #518305

# Submission time Handle Problem Language Result Execution time Memory
518305 2022-01-23T10:56:45 Z Be_dos XOR Sum (info1cup17_xorsum) C++17
100 / 100
 568 ms 17576 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>

int32_t pairs_big_sum(int32_t* arr, int32_t n, int32_t target_sum) {
    int32_t right_num = 0;
    int64_t ans = 0;
    for(int32_t i = 0; i < n; i++) {
        if(arr[i] + arr[i] >= target_sum)
            ans++;
        while(right_num < n && arr[i] + arr[n - right_num - 1] >= target_sum)
            right_num++;
        ans += right_num;
    }
    return (ans / 2) % 2;
}

int32_t pairs_small_sum(int32_t* arr, int32_t n, int32_t* arr2, int32_t m, int32_t target_sum) {
    int32_t second_num = 0;
    while(second_num < m && arr[0] + arr2[second_num] <= target_sum)
        second_num++;
    int64_t ans = second_num;
    for(int32_t i = 1; i < n; i++) {
        while(second_num > 0 && arr[i] + arr2[second_num - 1] > target_sum)
            second_num--;
        ans += second_num;
    }
    return ans % 2;
}

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];

    /*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 << "\n";*/

    int32_t ans = 0;
    std::sort(arr, arr + n);
    int32_t* tmp = new int32_t[n];
    for(int32_t i = 30; i >= 0; i--) {
        int32_t num_0 = 0;
        for(int32_t j = 0; j < n; j++)
            if((arr[j] & (1 << i)) == 0)
                num_0++;
        if(pairs_big_sum(arr, num_0, 1 << i) % 2 == 1)
            ans ^= 1 << i;
        for(int32_t j = num_0; j < n; j++)
            arr[j] &= INT32_MAX - (1 << i);
        if(pairs_big_sum(arr + num_0, n - num_0, 1 << i) % 2 == 1)
            ans ^= 1 << i;
        if(pairs_small_sum(arr, num_0, arr + num_0, n - num_0, (1 << i) - 1) % 2 == 1)
            ans ^= 1 << i;

        if(i > 0) {
            int32_t num_00 = 0, num_01 = 0, num_10 = 0, num_11 = 0;
            for(int32_t j = 0; j < num_0; j++)
                if(arr[j] & (1 << (i - 1)))
                    num_01++;
                else
                    num_00++;
            for(int32_t j = num_0; j < n; j++)
                if(arr[j] & (1 << (i - 1)))
                    num_11++;
                else
                    num_10++;
            std::merge(arr, arr + num_00, arr + num_0, arr + num_0 + num_10, tmp);
            std::merge(arr + num_00, arr + num_0, arr + num_0 + num_10, arr + n, tmp + num_00 + num_10);
            for(int32_t j = 0; j < n; j++)
                arr[j] = tmp[j];
        }
    }

    std::cout << ans << "\n";
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 320 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 8136 KB Output is correct
2 Correct 247 ms 7920 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 8136 KB Output is correct
2 Correct 247 ms 7920 KB Output is correct
3 Correct 358 ms 8516 KB Output is correct
4 Correct 343 ms 8236 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 320 KB Output is correct
3 Correct 58 ms 1348 KB Output is correct
4 Correct 60 ms 1468 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 320 KB Output is correct
3 Correct 265 ms 8136 KB Output is correct
4 Correct 247 ms 7920 KB Output is correct
5 Correct 358 ms 8516 KB Output is correct
6 Correct 343 ms 8236 KB Output is correct
7 Correct 58 ms 1348 KB Output is correct
8 Correct 60 ms 1468 KB Output is correct
9 Correct 565 ms 8524 KB Output is correct
10 Correct 568 ms 17576 KB Output is correct
11 Correct 546 ms 17372 KB Output is correct