Submission #389319

#TimeUsernameProblemLanguageResultExecution timeMemory
389319syl123456XOR Sum (info1cup17_xorsum)C++17
100 / 100
1089 ms22284 KiB
#include <bits/stdc++.h> #define all(i) (i).begin(), (i).end() #define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl using namespace std; template<typename T1, typename T2> ostream& operator << (ostream &i, pair<T1, T2> j) { return i << j.first << ' ' << j.second; } template<typename T> ostream& operator << (ostream &i, vector<T> j) { i << '{' << j.size() << ':'; for (T ii : j) i << ' ' << ii; return i << '}'; } typedef long long ll; typedef pair<int, int> pi; typedef pair<pi, int> pp; int main() { ios::sync_with_stdio(0), cin.tie(0); int n; cin >> n; int _mx = 0; vector<int> a(n); for (int &i : a) cin >> i, _mx = max(_mx, i); int ans = 0; for (int i = 0; i < 30; ++i) { vector<int> v[2], q, q2; for (int j : a) v[j >> i & 1].push_back(j); int it = 0; for (int j : v[0]) a[it++] = j; for (int j : v[1]) a[it++] = j; int x = (1 << i + 1) - 1; ll tmp = 0; for (int j : v[1]) { j &= x; if (j << 1 & 1 << i) ++tmp; q.push_back(x - j);//+ q2.push_back(x + (1 << i) - j);//- tmp += (int)v[1].size(); } for (int j = 0; j <= v[0].size(); ++j) while (!q.empty() && (j == v[0].size() || q.back() < (v[0][j] & x))) tmp += j, q.pop_back(); for (int j = 0; j <= v[1].size(); ++j) while (!q2.empty() && (j == v[1].size() || q2.back() < (v[1][j] & x))) tmp -= j, q2.pop_back(); for (int j : v[0]) { j &= x; if (j << 1 & 1 << i) ++tmp; q.push_back(x - j);//+ q2.push_back((x >> 1) - j);//- tmp += (int)v[0].size(); } for (int j = 0; j <= v[1].size(); ++j) while (!q.empty() && (j == v[1].size() || q.back() < (v[1][j] & x))) tmp += j, q.pop_back(); for (int j = 0; j <= v[0].size(); ++j) while (!q2.empty() && (j == v[0].size() || q2.back() < (v[0][j] & x))) tmp -= j, q2.pop_back(); if (tmp & 2) ans ^= 1 << i; } cout << ans; }

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:32:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   32 |         int x = (1 << i + 1) - 1;
      |                       ~~^~~
xorsum.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j = 0; j <= v[0].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~
xorsum.cpp:42:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while (!q.empty() && (j == v[0].size() || q.back() < (v[0][j] & x))) tmp += j, q.pop_back();
      |                                   ~~^~~~~~~~~~~~~~
xorsum.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int j = 0; j <= v[1].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~
xorsum.cpp:44:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             while (!q2.empty() && (j == v[1].size() || q2.back() < (v[1][j] & x))) tmp -= j, q2.pop_back();
      |                                    ~~^~~~~~~~~~~~~~
xorsum.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int j = 0; j <= v[1].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~
xorsum.cpp:53:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             while (!q.empty() && (j == v[1].size() || q.back() < (v[1][j] & x))) tmp += j, q.pop_back();
      |                                   ~~^~~~~~~~~~~~~~
xorsum.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int j = 0; j <= v[0].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~
xorsum.cpp:55:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             while (!q2.empty() && (j == v[0].size() || q2.back() < (v[0][j] & x))) tmp -= j, q2.pop_back();
      |                                    ~~^~~~~~~~~~~~~~
#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...