Submission #389319

#	Time	Username	Problem	Language	Result	Execution time	Memory
389319		syl123456	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	1089 ms	22284 KiB

xorsum

#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();
      |                                    ~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23