Submission #1139821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139821		Muhammet	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	608 ms	26400 KiB

xorsum

#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define SZ(s) (int)s.size()
#define ff first
#define ss second

const int N = 205;

ll T, n;

vector <ll> a, o, z;

ll f0(ll x){
    ll ind = SZ(z), ans = 0;
    for(int i = 0; i < SZ(z); i++){
        while(ind > 0 and (z[ind-1] + z[i]) >= (1<<x)) ind--;
        ans += (SZ(z)-ind);
        ans += ((z[i]*2) >= (1<<x));
    }
    ans /= 2;
    ind = SZ(o);
    ll ans1 = 0;
    for(int i = 0; i < SZ(o); i++){
        while(ind > 0 and (o[ind-1] + o[i]) >= (1<<x)) ind--;
        ans1 += (SZ(o)-ind);
        ans1 += ((o[i]*2) >= (1<<x));
    }
    ans1 /= 2;
    return ans + ans1;
}

ll f1(ll x){
    ll ind = SZ(z), ans = 0;
    for(int i = 0; i < SZ(o); i++){
        while(ind > 0 and ((z[ind-1] + o[i])>>x)&1) ind--;
        ans += ind;
    }
    return ans;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n;
    a.resize(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    ll ans = 0;

    for(int x = 0; x < 31; x++){
        o.clear(), z.clear();
        for(int i = 0; i < n; i++){
            if((a[i]>>x)&1) o.push_back(a[i]);
            else z.push_back(a[i]);
        }
        a.clear();
        for(auto i : z) a.push_back(i);
        for(auto i : o) a.push_back(i);
        for(int i = 0; i < SZ(z); i++){
            z[i] %= (1<<x);
        }
        for(int i = 0; i < SZ(o); i++){
            o[i] %= (1<<x);
        }
        ll cnt = f0(x);
        cnt += f1(x);
        if(cnt % 2 == 1) ans += (1<<x);
    }

    cout << ans;

	return 0;
}

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