Submission #518299

#TimeUsernameProblemLanguageResultExecution timeMemory
518299Be_dosXOR Sum (info1cup17_xorsum)C++17
77 / 100
1655 ms13484 KiB
#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; for(int32_t i = 29; i >= 0; i--) { std::sort(arr, arr + n); 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; } std::cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...