oj.uz

Submission #389302

# Submission time Handle Problem Language Result Execution time Memory
389302 2021-04-14T02:27:02 Z balbit XOR Sum (info1cup17_xorsum) C++14
45 / 100
 1600 ms 12396 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
//#ifndef BALBIT
//#include "grader.h"
//#endif

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBITs

int re = 0;
//
//vector<int> y1, y0;

void go(vector<int> &v, int bit) {
    vector<int> y1, y0;
    for (int &x : v) {
        if (x & (1<<bit)) {
            x ^= (1<<bit);
            y1.pb(x);
        }else{
            y0.pb(x);
        }
    }
    sort(ALL(y1)); sort(ALL(y0));
//    if ((SZ(y1)*(ll)(SZ(y1)+1)/2) & 1) re^=(1<<(bit+1));
    if (bit == 0) {
        if ((SZ(y1)&1) && (SZ(y0)&1)) {
            re ^= 1;
        }
        return;
    }
    if (SZ(y1) && SZ(y0)) {
        bool over = 0;
        int j = SZ(y0);
        REP(i, SZ(y1)) {
            while (j-1>=0 && y0[j-1] + y1[i] >= (1<<bit)) {
                --j;
            }
            over ^= (SZ(y0) - j)&1;
        }
//        if (over) re ^= (1<<(bit+1));
        if (((SZ(y0) * (ll)(SZ(y1))) ^ over)&1) {
            re ^= 1<<bit;
        }
    }
    if (SZ(y1)) {
        int j = SZ(y1);
        bool over = 0;
        REP(i, SZ(y1)) {
            while (j-1 >= i && y1[j-1] + y1[i] >= (1<<bit)) --j;
            if (i > j) j=i;
            over ^= (SZ(y1) - j) &1;
        }
        if (over) re ^= (1<<bit);
    }
    if (SZ(y0)) {
        int j = SZ(y0);
        bool over = 0;
        REP(i, SZ(y0)) {
            while (j-1 >= i && y0[j-1] + y0[i] >= (1<<bit)) --j;
            if (i > j) j =i;
            over ^= (SZ(y0) - j) &1;
        }
        if (over) re ^= (1<<bit);
    }
    //    if (SZ(y1)) go(y1, bit-1);
//    if (SZ(y0)) go(y0, bit-1);
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin>>n;
    vector<int> x(n);
    REP(i,n) cin>>x[i];
    for (int i = 30; i>=0; --i) {
        go(x,i);
    }
    cout<<re<<endl;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 10 ms 364 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1672 ms 12396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1672 ms 12396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 10 ms 364 KB Output is correct
3 Correct 251 ms 1628 KB Output is correct
4 Correct 247 ms 1640 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 332 KB Output is correct
2 Correct 10 ms 364 KB Output is correct
3 Execution timed out 1672 ms 12396 KB Time limit exceeded
4 Halted 0 ms 0 KB -