Submission #1141831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141831		Math4Life2020	Circle selection (APIO18_circle_selection)	C++20	Compilation error	0 ms	0 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>; using ui = long long;

const ll Nm = 3e5+5; const ll E = 32;
set<pii> sact; //{-rad,indx}
ll ans[Nm];
ll x[Nm];
ll y[Nm];
ll r[Nm];

struct Node {
    unordered_set<int> selem;
    ll xc;
    ll yc;
    ll ec;
    Node* cld[2][2];
    Node(ll _xc, ll _yc, ll _ec, vector<ll> _ve) {
        cld[0][0]=nullptr;
        cld[0][1]=nullptr;
        cld[1][0]=nullptr;
        cld[1][1]=nullptr;
        for (ll x0: _ve) {
            selem.insert(x0);
        }
        xc = _xc;
        yc = _yc;
        ec = _ec;
       // cout << "created node with xc,yc,ec="<<xc<<","<<yc<<","<<ec<<"\n";
    }
    void pdn(ll e0) {
        if (e0<ec) {
            for (ll i=0;i<2;i++) {
                for (ll j=0;j<2;j++) {
                    if (cld[i][j]!=nullptr) {
                        cld[i][j]->pdn(e0);
                    }
                }
            }
            return;
        }
        vector<ll> vpd[2][2];
        for (ll i: selem) {
           // cout << "new eval = "<<(ec-1)<<"\n";
            //cout << "ymod val: y="<<y[i]<<"\n";
            //cout << "div result: "<<(y[i]>>(ec-1))<<"\n";
            vpd[(x[i]>>(ec-1))%2][(y[i]>>(ec-1))%2].push_back(i);
        }
        selem.clear();
        selem.rehash(1);
        for (ll i=0;i<2;i++) {
            for (ll j=0;j<2;j++) {
                if (!vpd[i][j].empty()) {
                    cld[i][j]= new Node(2*xc+i,2*yc+j,ec-1,vpd[i][j]);
                }
            }
        }
    }
    void get(ll x0, ll y0, ll e0, ll i0) {
       // cout << "get: x0,y0,e0="<<x0<<","<<y0<<","<<e0<<"\n";
        //cout << "at: xc,yc,ec="<<xc<<","<<yc<<","<<ec<<"\n";
        if (e0==ec) {
            if (x0==xc && y0==yc) {
                vector<ll> vget;
                for (ll x1: selem) {
                    //cout << "push back!\n";
                    vget.push_back(x1);
                }
                for (ll j0: vget) {
                    ui dx = (x[j0]-x[i0]); dx = dx*dx;
                    ui dy = (y[j0]-y[i0]); dy = dy*dy;
                    ui dr = (r[i0]+r[j0]); dr = dr*dr;
                    if ((dx+dy)<=dr) {
                        ans[j0]=i0+1;
                        sact.erase(sact.find({-r[j0],j0}));
                        selem.erase(j0);
                    } 
                }
            }
        } else {
            assert(ec>e0);
            //cout << (x0>>(ec-e0)) << " = test val \n";
            if ((x0>>(ec-e0))==xc && (y0>>(ec-e0))==yc) {
                for (ll i=0;i<2;i++) {
                    for (ll j=0;j<2;j++) {
                        if (cld[i][j]!=nullptr) {
                            cld[i][j]->get(x0,y0,e0,i0);
                        }
                    }
                }
            }
        }
    }
};

inline ll l2(ll x) {
    return (63LL-__builtin_clzll(x));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    ll N; cin >> N;
    vector<ll> vi0;
    for (ll i=0;i<N;i++) {
        cin >> x[i] >> y[i] >> r[i];
        x[i]+=((ll)1e9);
        y[i]+=((ll)1e9);
        sact.insert({-r[i],i});
        vi0.push_back(i);
    }
    ll EC = E;
    Node* rt = new Node(0,0,E,vi0);
    while (sact.size()!=0) {
        auto A0 = *sact.begin();
        ll i = A0.second;
        ll L = 2+l2(2*r[i]+1);
        while (L<EC) {
            rt->pdn(EC);
            EC--;
        }
        ll nx = (x[i]-2*r[i]-1)>>L; nx = max(nx,0LL);
        ll ny = (y[i]-2*r[i]-1)>>L; ny = max(ny,0LL);
       // cout << "nx,ny,L="<<nx<<","<<ny<<","<<L<<"\n";
        assert(x[i]>=(nx<<L));
        assert(x[i]<((nx+2)<<L));
        assert(y[i]>=(ny<<L));
        assert(y[i]<((ny+2)<<L));
        rt->get(nx,ny,L,i);
        rt->get(nx,ny+1,L,i);
        rt->get(nx+1,ny,L,i); 
        rt->get(nx+1,ny+1,L,i);
        // ui dx = (x[j]-x[i]); dx = dx*dx;
        // ui dy = (y[j]-y[i]); dy = dy*dy;
        // ui dr = (r[i]+r[j]); dr = dr*dr;
        // if ((dx+dy)<=dr) {
        //     ans[j]=i+1;
        //     sact.erase(sact.find({-r[j],j}));
        //     rt->del((x[j]),(y[j]),L,j);
        // }
    }
    for (ll i=0;i<N;i++) {
        cout << ans[i];
        if (i!=(N-1)) {
            cout << " ";
        }
    }
    cout << "\n";
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:121:45: error: no matching function for call to 'max(ll&, long long int)'
  121 |         ll nx = (x[i]-2*r[i]-1)>>L; nx = max(nx,0LL);
      |                                          ~~~^~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from circle_selection.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
circle_selection.cpp:121:45: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  121 |         ll nx = (x[i]-2*r[i]-1)>>L; nx = max(nx,0LL);
      |                                          ~~~^~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from circle_selection.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
circle_selection.cpp:121:45: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  121 |         ll nx = (x[i]-2*r[i]-1)>>L; nx = max(nx,0LL);
      |                                          ~~~^~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from circle_selection.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
circle_selection.cpp:121:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  121 |         ll nx = (x[i]-2*r[i]-1)>>L; nx = max(nx,0LL);
      |                                          ~~~^~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from circle_selection.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
circle_selection.cpp:121:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  121 |         ll nx = (x[i]-2*r[i]-1)>>L; nx = max(nx,0LL);
      |                                          ~~~^~~~~~~~
circle_selection.cpp:122:45: error: no matching function for call to 'max(ll&, long long int)'
  122 |         ll ny = (y[i]-2*r[i]-1)>>L; ny = max(ny,0LL);
      |                                          ~~~^~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from circle_selection.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
circle_selection.cpp:122:45: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  122 |         ll ny = (y[i]-2*r[i]-1)>>L; ny = max(ny,0LL);
      |                                          ~~~^~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from circle_selection.cpp:1:
/usr/include/c++/11/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++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
circle_selection.cpp:122:45: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  122 |         ll ny = (y[i]-2*r[i]-1)>>L; ny = max(ny,0LL);
      |                                          ~~~^~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from circle_selection.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
circle_selection.cpp:122:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  122 |         ll ny = (y[i]-2*r[i]-1)>>L; ny = max(ny,0LL);
      |                                          ~~~^~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from circle_selection.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
circle_selection.cpp:122:45: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  122 |         ll ny = (y[i]-2*r[i]-1)>>L; ny = max(ny,0LL);
      |                                          ~~~^~~~~~~~