답안 #389319

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389319 2021-04-14T02:57:11 Z syl123456 XOR Sum (info1cup17_xorsum) C++17
100 / 100
1089 ms 22284 KB
#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

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();
      |                                    ~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 404 KB Output is correct
2 Correct 5 ms 404 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 892 ms 22160 KB Output is correct
2 Correct 834 ms 21328 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 892 ms 22160 KB Output is correct
2 Correct 834 ms 21328 KB Output is correct
3 Correct 928 ms 22168 KB Output is correct
4 Correct 884 ms 21764 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 404 KB Output is correct
2 Correct 5 ms 404 KB Output is correct
3 Correct 109 ms 2648 KB Output is correct
4 Correct 111 ms 2636 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 404 KB Output is correct
2 Correct 5 ms 404 KB Output is correct
3 Correct 892 ms 22160 KB Output is correct
4 Correct 834 ms 21328 KB Output is correct
5 Correct 928 ms 22168 KB Output is correct
6 Correct 884 ms 21764 KB Output is correct
7 Correct 109 ms 2648 KB Output is correct
8 Correct 111 ms 2636 KB Output is correct
9 Correct 1089 ms 22244 KB Output is correct
10 Correct 1076 ms 22284 KB Output is correct
11 Correct 1082 ms 22188 KB Output is correct