Submission #1009186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009186		Khanhcsp2	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	460 ms	25388 KiB

xorsum

#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define int ll
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
const int mod=1e9+7;
const int N=1e6+11;
int n, a[N], b[N], ans, p1, p2, p3;
void ss(int bit)
{
    for(int i=1;i<=n;i++) b[i]=a[i];
    int id=1;
    while(id<=n)
    {
        if(b[id]>=(1<<(bit+1))) break;
        id++;
    }
    for(int i=id;i<=n;i++) b[i]%=(1<<(bit+1));
    int s1=1, s2=id, run=0;
    while(s1+1<=id && s2<=n)
    {
        if(b[s1]<=b[s2]) a[++run]=b[s1++];
        else a[++run]=b[s2++];
    }
    while(s1+1<=id) a[++run]=b[s1++];
    while(s2<=n) a[++run]=b[s2++];
}
void sol()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(a+1, a+n+1);
    for(int bit=30;bit>=0;bit--)
    {
        ss(bit);
        p1=p2=p3=n+1;
        for(int i=1;i<=n;i++)
        {
//             2^bit <= a[i]+a[p1] <= 2*2^bit-1
//             2*2^bit <= a[i]+a[p2] <= 3*2^bit-1
//             3*2^bit<= a[i]+a[p3] <= 4*2^bit-1
            p1=max(p1, i), p2=max(p2, i), p3=max(p3, i);
            while(i+1<=p1 && 1*(1<<bit)<=a[i]+a[p1-1]) p1--;
            while(i+1<=p2 && 2*(1<<bit)<=a[i]+a[p2-1]) p2--;
            while(i+1<=p3 && 3*(1<<bit)<=a[i]+a[p3-1]) p3--;
            if((n-p1+p2-p3)%2==0) ans=ans^(1<<bit);
        }
    }
    cout << ans;
}
signed main()
{
//    freopen("divisor.INP", "r", stdin);
//    freopen("divisor.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while(t--)
    {
        sol();
    }
}

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