Submission #982383

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
982383	2024-05-14T07:52:47 Z	Muhammad_Aneeq	Circle selection (APIO18_circle_selection)	C++17	Compilation error	0 ms	0 KB

circle_selection

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define int long long
int man(pair<int,int>a,pair<int,int>b)
{
    return ((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
inline void solve()
{
    int n;
    cin>>n;
    pair<int,int>a[n];
    bool w=0;
    set<pair<int,int>>s;
    int ra[n]={};
    for (int i=0;i<n;i++)
    {
        int x,y,r;
        cin>>x>>y>>r;
        a[i]={x,y};
        if (y!=0)
            w=1;
        s.insert({-r,i});
        ra[i]=r;
    }  
    if (w==0)
    {
        set<pair<int,int>>val;
        for (int i=0;i<n;i++)
        {
            val.insert({a[i].first,i});
            val.insert({a[i].first+ra[i],i});
            val.insert({a[i].first-ra[i],i});
        }
        while (s.size())
        {
            int i=(*begin(s)).second;
            s.erase(*begin(s));
            auto lb=val.lower_bound(a[i].first-ra[i]);
            set<int>z;
            while (lb!=val.end()&&(*lb).first<=a[i].first+ra[i])
                z.insert((*lb).second);
            for (auto j:z)
            {
                val.insert({a[j].first,j});
                val.insert({a[j].first+ra[j],j});
                val.insert({a[j].first-ra[j],j});
                ans[j]=i;
            }
        }
        for (auto i:ans)
            cout<<i+1<<' ';
        cout<<endl;
    }
    else
    {
        int ans[n]={};
        while (s.size())
        {
            int r=(*begin(s)).first,i=(*begin(s)).second;
            s.erase(*begin(s));
            ans[i]=i;
            vector<pair<int,int>>z;
            for (auto [r1,j]:s)
            {
                int dis=man(a[i],a[j]);
                if (dis<=((r+r1)*(r+r1)))
                    z.push_back({r1,j});
                if (z.size()&&n>5000)
                    break;
            }
            for (auto j:z)
            {
                ans[j.second]=i;
                s.erase(j);
            }
        }
        for (auto i:ans)
            cout<<i+1<<' ';
        cout<<endl;
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

Compilation message

circle_selection.cpp: In function 'void solve()':
circle_selection.cpp:49:53: error: no matching function for call to 'std::set<std::pair<long long int, long long int> >::lower_bound(long long int)'
   49 |             auto lb=val.lower_bound(a[i].first-ra[i]);
      |                                                     ^
In file included from /usr/include/c++/10/set:61,
                 from circle_selection.cpp:8:
/usr/include/c++/10/bits/stl_set.h:829:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
  829 |       lower_bound(const key_type& __x)
      |       ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:829:35: note:   no known conversion for argument 1 from 'long long int' to 'const key_type&' {aka 'const std::pair<long long int, long long int>&'}
  829 |       lower_bound(const key_type& __x)
      |                   ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:833:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::const_iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) const [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
  833 |       lower_bound(const key_type& __x) const
      |       ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:833:35: note:   no known conversion for argument 1 from 'long long int' to 'const key_type&' {aka 'const std::pair<long long int, long long int>&'}
  833 |       lower_bound(const key_type& __x) const
      |                   ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:839:2: note: candidate: 'template<class _Kt> decltype ((std::set<_Key, _Compare, _Alloc>::iterator)(((std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_lower_bound_tr(__x))) std::set<_Key, _Compare, _Alloc>::lower_bound(const _Kt&) [with _Kt = _Kt; _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
  839 |  lower_bound(const _Kt& __x)
      |  ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:839:2: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_set.h: In substitution of 'template<class _Kt> decltype ((std::set<std::pair<long long int, long long int> >::iterator)(((std::set<std::pair<long long int, long long int> >*)this)->std::set<std::pair<long long int, long long int> >::_M_t.std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::_M_lower_bound_tr(__x))) std::set<std::pair<long long int, long long int> >::lower_bound<_Kt>(const _Kt&) [with _Kt = long long int]':
circle_selection.cpp:49:53:   required from here
/usr/include/c++/10/bits/stl_set.h:840:45: error: no matching function for call to 'std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::_M_lower_bound_tr(const long long int&)'
  840 |  -> decltype(iterator(_M_t._M_lower_bound_tr(__x)))
      |                       ~~~~~~~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/10/set:60,
                 from circle_selection.cpp:8:
/usr/include/c++/10/bits/stl_tree.h:1330:2: note: candidate: 'template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound_tr(const _Kt&) [with _Kt = _Kt; _Req = _Req; _Key = std::pair<long long int, long long int>; _Val = std::pair<long long int, long long int>; _KeyOfValue = std::_Identity<std::pair<long long int, long long int> >; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
 1330 |  _M_lower_bound_tr(const _Kt& __k)
      |  ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h:1330:2: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_tree.h: In substitution of 'template<class _Cmp, class _SfinaeType> using __has_is_transparent_t = typename std::__has_is_transparent<_Cmp, _SfinaeType>::type [with _Cmp = std::less<std::pair<long long int, long long int> >; _SfinaeType = long long int]':
/usr/include/c++/10/bits/stl_tree.h:1328:9:   required by substitution of 'template<class _Kt> decltype ((std::set<std::pair<long long int, long long int> >::iterator)(((std::set<std::pair<long long int, long long int> >*)this)->std::set<std::pair<long long int, long long int> >::_M_t.std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::_M_lower_bound_tr(__x))) std::set<std::pair<long long int, long long int> >::lower_bound<_Kt>(const _Kt&) [with _Kt = long long int]'
circle_selection.cpp:49:53:   required from here
/usr/include/c++/10/bits/stl_tree.h:429:11: error: no type named 'type' in 'struct std::__has_is_transparent<std::less<std::pair<long long int, long long int> >, long long int, void>'
  429 |     using __has_is_transparent_t
      |           ^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h: In substitution of 'template<class _Kt> decltype ((std::set<std::pair<long long int, long long int> >::iterator)(((std::set<std::pair<long long int, long long int> >*)this)->std::set<std::pair<long long int, long long int> >::_M_t.std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::_M_lower_bound_tr(__x))) std::set<std::pair<long long int, long long int> >::lower_bound<_Kt>(const _Kt&) [with _Kt = long long int]':
circle_selection.cpp:49:53:   required from here
/usr/include/c++/10/bits/stl_tree.h:1339:2: note: candidate: 'template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound_tr(const _Kt&) const [with _Kt = _Kt; _Req = _Req; _Key = std::pair<long long int, long long int>; _Val = std::pair<long long int, long long int>; _KeyOfValue = std::_Identity<std::pair<long long int, long long int> >; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
 1339 |  _M_lower_bound_tr(const _Kt& __k) const
      |  ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h:1339:2: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/10/set:61,
                 from circle_selection.cpp:8:
/usr/include/c++/10/bits/stl_set.h:845:2: note: candidate: 'template<class _Kt> decltype ((std::set<_Key, _Compare, _Alloc>::const_iterator)(((const std::set<_Key, _Compare, _Alloc>*)this)->std::set<_Key, _Compare, _Alloc>::_M_t._M_lower_bound_tr(__x))) std::set<_Key, _Compare, _Alloc>::lower_bound(const _Kt&) const [with _Kt = _Kt; _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
  845 |  lower_bound(const _Kt& __x) const
      |  ^~~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:845:2: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_set.h: In substitution of 'template<class _Kt> decltype ((std::set<std::pair<long long int, long long int> >::const_iterator)(((const std::set<std::pair<long long int, long long int> >*)this)->std::set<std::pair<long long int, long long int> >::_M_t.std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::_M_lower_bound_tr(__x))) std::set<std::pair<long long int, long long int> >::lower_bound<_Kt>(const _Kt&) const [with _Kt = long long int]':
circle_selection.cpp:49:53:   required from here
/usr/include/c++/10/bits/stl_set.h:846:51: error: no matching function for call to 'std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::_M_lower_bound_tr(const long long int&) const'
  846 |  -> decltype(const_iterator(_M_t._M_lower_bound_tr(__x)))
      |                             ~~~~~~~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/10/set:60,
                 from circle_selection.cpp:8:
/usr/include/c++/10/bits/stl_tree.h:1330:2: note: candidate: 'template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound_tr(const _Kt&) [with _Kt = _Kt; _Req = _Req; _Key = std::pair<long long int, long long int>; _Val = std::pair<long long int, long long int>; _KeyOfValue = std::_Identity<std::pair<long long int, long long int> >; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
 1330 |  _M_lower_bound_tr(const _Kt& __k)
      |  ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h:1330:2: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_tree.h:1339:2: note: candidate: 'template<class _Kt, class _Req> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::const_iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound_tr(const _Kt&) const [with _Kt = _Kt; _Req = _Req; _Key = std::pair<long long int, long long int>; _Val = std::pair<long long int, long long int>; _KeyOfValue = std::_Identity<std::pair<long long int, long long int> >; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >]'
 1339 |  _M_lower_bound_tr(const _Kt& __k) const
      |  ^~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h:1339:2: note:   template argument deduction/substitution failed:
circle_selection.cpp:58:17: error: 'ans' was not declared in this scope; did you mean 'abs'?
   58 |                 ans[j]=i;
      |                 ^~~
      |                 abs
circle_selection.cpp:61:21: error: 'ans' was not declared in this scope; did you mean 'abs'?
   61 |         for (auto i:ans)
      |                     ^~~
      |                     abs