Submission #687578

#	Time	Username	Problem	Language	Result	Execution time	Memory
687578		alexdd	XOR Sum (info1cup17_xorsum)	C++17	0 / 100	1665 ms	12712 KiB

xorsum

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000007;
int n;
int v[1000001];
int newv[1000001];
bitset<100000000> fr;
void precalc(int bit)
{
    for(int i=0;i<n;i++)
    {
        ///calc newv[i]
        v[i] = newv[i];
        for(int j=bit+1;j<=28;j++)
        {
            if(((1<<j)&(v[i]))!=0)
                v[i] -= (1<<j);
        }
    }
}
int qry(int x)///returneaza cate numere <= x apar in sirul modificat
{
    int cnt=0;
    for(int i=0;i<n;i++)
        if(v[i]<=x)
            cnt++;
    return cnt;
}
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];
    }
    int rez=0;
    for(int bit=0;bit<=28;bit++)
    {
        precalc(bit);
        int cntb=0;
        for(int i=0;i<n;i++)
        {
            int st1,dr1,st2,dr2;
            st1 = max(0, (1<<bit) - v[i]);
            dr1 = (1<<(bit+1)) - v[i] - 1;
            if(st1<=dr1)
                cntb += qry(dr1) - qry(st1-1);
            cntb%=2;
            st2 = (1<<bit) + (1<<(bit+1)) - v[i];
            dr2 = (1<<(bit+1))-1;
            if(st2<=dr2)
                cntb += qry(dr2) - qry(st2-1);
            cntb%=2;
        }
        cntb=cntb%2;
        if(cntb==1)
            rez += (1<<bit);
    }
    cout<<rez;
    return 0;
    for(int i=0;i<128;i++)
    {
        int inc=-1;
        cout<<i<<": \n";
        for(int j=0;j<128;j++)
        {
            if(((i+j)&(1<<6))!=0)
            {
                //cout<<i<<" "<<j<<"\n";
                if(inc==-1)
                    inc=j;
            }
            else if(j>0 && ((i+(j-1))&(1<<6))!=0)
            {
                cout<<inc<<" -> "<<j-1<<"\n";
                inc=-1;
            }
        }
        if(inc!=-1)
            cout<<inc<<" -> "<<127<<"\n";
        cout<<"\n\n\n";
    }

    return 0;
}

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