oj.uz

Submission #687617

# Submission time Handle Problem Language Result Execution time Memory
687617 2023-01-26T16:15:15 Z alexdd XOR Sum (info1cup17_xorsum) C++17
45 / 100
 1600 ms 8040 KB 
#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
int n;
int v[1000001];
int newv[1000001];
int mxm=0;
void precalc(int bit)
{
    mxm=0;
    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);
        }
        mxm=max(mxm, v[i]);
    }
    sort(v,v+n);
}
int qry(int x)///returneaza cate numere <= x apar in sirul modificat
{
    int st,dr,mij;
    if(v[0]>x)
        return 0;
    st=0;
    dr=n-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(v[mij]<=x && (mij==n-1 || v[mij+1]>x))
            return mij+1;
        else if(v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st+1;
    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;
        int cnt2=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;
            dr1 = min(dr1,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;
            dr2 = min(dr2, v[i]-1);
            if(st2<=dr2)
                cntb += qry(dr2) - qry(st2-1);
            cntb%=2;

            if(((1<<bit)&(v[i]+v[i]))!=0)
            {
                cnt2 += qry(v[i]) - qry(v[i]-1) - 1;
                cntb++;

                cntb%=2;
            }
        }
        cnt2/=2;
        cntb+=cnt2;
        cntb=cntb%2;
        if(cntb==1)
            rez += (1<<bit);
    }
    cout<<rez;
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 340 KB Output is correct
2 Correct 22 ms 364 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1688 ms 8040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1688 ms 8040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 340 KB Output is correct
2 Correct 22 ms 364 KB Output is correct
3 Correct 601 ms 1112 KB Output is correct
4 Correct 566 ms 2048 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 340 KB Output is correct
2 Correct 22 ms 364 KB Output is correct
3 Execution timed out 1688 ms 8040 KB Time limit exceeded
4 Halted 0 ms 0 KB -