oj.uz

Submission #886509

# Submission time Handle Problem Language Result Execution time Memory
886509 2023-12-12T09:10:01 Z AnhPham XOR Sum (info1cup17_xorsum) C++17
45 / 100
 240 ms 4780 KB 
#include <bits/stdc++.h>

#ifdef OP_DEBUG
    #include <algo/debug.h>
#else
    #define debug(...) 26
#endif

using namespace std;

#define int 	long long // maybe tle?
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
#define TcT     template <class T

const   int     MOD = (int)1e9 + 7, INF = (int)2e9 + 9, INF64 = (int)4e18 + 18;

TcT>            bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
TcT>            bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

TcT, class S>   istream &operator >> (istream &scanf, pair <T, S> &u) { return scanf >> u.first >> u.second;        }
TcT, class S>   ostream &operator << (ostream &print, pair <T, S> &u) { return print << u.first << ' ' << u.second; }

void solve();

int32_t main() {
    // freopen("input.inp", "r", stdin);
    // freopen("B.out", "w", stdout);

    cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(0);
    int testcases = 1;

#define TC 0
    if (TC) { cin >> testcases; } for (; testcases--;) { solve(); }
}

/* [Pham Hung Anh - 11I - Tran Hung Dao High School for Gifted Student] */

const int N = 3e5 + 5;

int n;
int a[N];

int check(int bit) {
    int cnt = 0;
    vector <int> rems;
    for (int i = 1; i <= n; ++i) {
        if ((a[i] & (1 << bit)) != 0)
            ++cnt;
        
        rems.push_back((a[i] % (1 << bit)));
    }

    sort(all(rems));

    int ans = (cnt * (n - cnt)) % 2;
    int r = n - 1;
    for (int l = 0; l < n; ++l) {
        if (l > r)
            ++r;
 
        while (r > l && rems[l] + rems[r - 1] >= (1 << bit))
            --r;
 
        if (rems[l] + rems[r] >= (1 << bit))
            ans = (ans + n - r) % 2;
    }

    return ans;
}

void solve() {
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    
    int ans = 0;
    for (int i = 0; i <= 40; ++i)
        if (check(i))
            ans |= (1 << i);
    
    cout << ans << '\n';
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 2692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 240 ms 4780 KB Output is correct
4 Correct 239 ms 4524 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Incorrect 19 ms 2692 KB Output isn't correct
4 Halted 0 ms 0 KB -