Submission #687645

#	Time	Username	Problem	Language	Result	Execution time	Memory
687645		alexdd	XOR Sum (info1cup17_xorsum)	C++17	Compilation error	0 ms	0 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 newv[1000001];
bool bl[1000001];
int sum[1000001];
unordered_map<int,int> fr;
int mxm=0;
void precalc(int bit)
{
    if(n>100000)
        for(int i=0;i<=1000000;i++)
            bl[i]=0,sum[i]=0;
    mxm=0;
    fr.clear();
    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]);
        if(((1<<bit)&(v[i]+v[i]))!=0)
            fr[v[i]]++;
        if(n>100000)
        {
            sum[v[i]]++;
            bl[v[i]] = !bl[v[i]];
        }
    }
    if(n<=100000)
        sort(v,v+n);
    else
    {
        for(int i=1;i<=1000000;i++)
        {
            if(bl[i-1])
                bl[i]=!bl[i];
            sum[i]=sum[i-1]+sum[i];
        }
    }
}
int qry(int x)///returneaza cate numere <= x apar in sirul modificat
{
    if(x<0)
        return 0;
    if(n<=100000)
    {
        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;
    }

    return sum[x];

    if(bl[x])
        return 1;
    return 0;
}
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 += 2 + 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 += 2 + qry(dr2) - qry(st2-1);
            cntb%=2;

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

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

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:98:41: error: no matching function for call to 'max(int, long long int)'
   98 |             st1 = max(0, (1<<bit) - v[i]);
      |                                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from xorsum.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
xorsum.cpp:98:41: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   98 |             st1 = max(0, (1<<bit) - v[i]);
      |                                         ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from xorsum.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
xorsum.cpp:98:41: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   98 |             st1 = max(0, (1<<bit) - v[i]);
      |                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from xorsum.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
xorsum.cpp:98:41: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   98 |             st1 = max(0, (1<<bit) - v[i]);
      |                                         ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from xorsum.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
xorsum.cpp:98:41: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   98 |             st1 = max(0, (1<<bit) - v[i]);
      |                                         ^