Submission #687666

#	Time	Username	Problem	Language	Result	Execution time	Memory
687666		alexdd	XOR Sum (info1cup17_xorsum)	C++17	7 / 100	1691 ms	25728 KiB

xorsum

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
int n;
int v[1000001];
int pre[1000001];
int newv[1000001];
bitset<5000005> bl;
unordered_map<int,int> fr;
map<int,int> used;
unordered_map<int,int> unde;
int mxm=0;
void precalc(int bit)
{
    used.clear();
    unde.clear();
    bl.reset();
    mxm=0;
    fr.clear();
    for(int i=0;i<n;i++)
    {
        ///calc v[i]
        if(((1<<bit)&(newv[i]))!=0)
            pre[i] = ((pre[i]) | (1<<bit));
        v[i] = pre[i];
        mxm=max(mxm, v[i]);
        if(((1<<bit)&(v[i]+v[i]))!=0)
            fr[v[i]]++;
        used[v[i]]=1;
    }
    for(int i=0;i<n;i++)
    {
        int st1,dr1,st2,dr2;
        st1 = max((int)0, (1<<bit) - v[i]);
        dr1 = (1<<(bit+1)) - v[i] - 1;
        dr1 = min(dr1,v[i]-1);
        if(st1<=dr1)
        {
            used[dr1]=1;
            used[st1-1]=1;
        }
        st2 = (1<<bit) + (1<<(bit+1)) - v[i];
        dr2 = (1<<(bit+1))-1;
        dr2 = min(dr2, v[i]-1);
        if(st2<=dr2)
        {
            used[dr2]=1;
            used[st2-1]=1;
        }
    }
    int cate=0;
    for(auto it:used)
    {
        cate++;
        unde[it.first]=cate;
    }
    for(int i=0;i<n;i++)
        bl[unde[v[i]]]=!bl[unde[v[i]]];
    for(int i=1;i<=cate;i++)
        bl[i] = (bl[i] ^ bl[i-1]);
}
int qry(int x)///returneaza cate numere <= x apar in sirul modificat
{
    if(x<0)
        return 0;
    return bl[x];
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
        newv[i] = v[i];
        pre[i]=0;
    }
    int rez=0;
    for(int bit=0;bit<=28;bit++)
    {
        precalc(bit);
        int cntb=0;
        int cnt2=0;
        for(int i=0;i<n;i++)
        {
            int st1,dr1,st2,dr2;
            st1 = max((int)0, (1<<bit) - v[i]);
            dr1 = (1<<(bit+1)) - v[i] - 1;
            dr1 = min(dr1,v[i]-1);
            if(st1<=dr1)
                cntb += 2 + qry(unde[dr1]) - qry(unde[st1-1]);
            cntb%=2;
            st2 = (1<<bit) + (1<<(bit+1)) - v[i];
            dr2 = (1<<(bit+1))-1;
            dr2 = min(dr2, v[i]-1);
            if(st2<=dr2)
                cntb += 2 + qry(unde[dr2]) - qry(unde[st2-1]);
            cntb%=2;

            if(((1<<bit)&(v[i]+v[i]))!=0)
            {
                cnt2 += fr[v[i]] - 1;
                cnt2 %= 4;
                cntb++;
                cntb%=2;
            }
        }
        cnt2/=2;
        cntb+=cnt2;
        cntb=cntb%2;
        if(cntb==1)
            rez += (1<<bit);
    }
    cout<<rez;
    return 0;
}

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