Submission #1090198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090198		TrinhKhanhDung	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	654 ms	31476 KiB

xorsum

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 1e6 + 10;

int N;
int a[MAX];

void solve(){
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> a[i];

    int ans = 0;
    for(int j = 0; j < 30; j++){
        vector<vector<int>> pre(2, vector<int>(N + 3, 0));
        for(int i = 1; i <= N; i++){
            pre[0][i] = pre[0][i - 1];
            pre[1][i] = pre[1][i - 1];
            pre[BIT(a[i], j)][i]++;
        }

        ll sum = 0;
        int k = 1;
        for(int i = N; i >= 1; i--){
            int cur = (MASK(j) - 1) & a[i];
            minimize(k, i);
            while(k <= i && ((MASK(j) - 1) & a[k]) + cur < MASK(j)) k++;
            int b = BIT(a[i], j);
            sum += (pre[!b][k - 1]) + (pre[b][i] - pre[b][k - 1]);
        }

        vector<int> t[2];
        for(int i = 1; i <= N; i++){
            t[BIT(a[i], j)].push_back(a[i]);
        }

        for(int i = 1; i <= sz(t[0]); i++){
            a[i] = t[0][i - 1];
        }
        for(int i = sz(t[0]) + 1; i <= N; i++){
            a[i] = t[1][i - sz(t[0]) - 1];
        }

        if(sum & 1) ans += MASK(j);
    }

    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    //i freopen("order.inp","r",stdin);
    // freopen("order.out","w",stdout);

    solve();

    return 0;
}

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