oj.uz

Submission #389307

# Submission time Handle Problem Language Result Execution time Memory
389307 2021-04-14T02:37:35 Z balbit XOR Sum (info1cup17_xorsum) C++14
100 / 100
 690 ms 12376 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);
        }
    }
    {
        int at = 0;
        int j = 0;
        REP(i, SZ(y0)) {
            while (j < SZ(y1) && y1[j] <= y0[i]) v[at++] = y1[j++];
            v[at++] = y0[i];
        }
//        while (j < SZ(y1)) v[at++] = y1[j++];
//        bug("oo");
//        for (int x : y0) cout<<x<<' ';
//        cout<<endl;
//        for (int x : y1) cout<<x<<' ';
//        cout<<endl;
//        for (int x : v) cout<<x<<' ';
//        cout<<endl;
    }
//    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];
    sort(ALL(x));
    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 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 12260 KB Output is correct
2 Correct 422 ms 11816 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 12260 KB Output is correct
2 Correct 422 ms 11816 KB Output is correct
3 Correct 542 ms 12376 KB Output is correct
4 Correct 519 ms 11992 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 71 ms 1592 KB Output is correct
4 Correct 73 ms 1732 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 458 ms 12260 KB Output is correct
4 Correct 422 ms 11816 KB Output is correct
5 Correct 542 ms 12376 KB Output is correct
6 Correct 519 ms 11992 KB Output is correct
7 Correct 71 ms 1592 KB Output is correct
8 Correct 73 ms 1732 KB Output is correct
9 Correct 687 ms 12244 KB Output is correct
10 Correct 685 ms 12264 KB Output is correct
11 Correct 690 ms 12224 KB Output is correct