oj.uz

Submission #106549

# Submission time Handle Problem Language Result Execution time Memory
106549 2019-04-19T03:33:28 Z username Circle selection (APIO18_circle_selection) C++14
Compilation error
 0 ms 0 KB 
#include<bits/stdc++.h>
#define int int64_t
using namespace std;
typedef pair<int,int> pii;
#define REP(i,j,k) for(int i=(j);i<(k);++i)
#define pb push_back
#define F first
#define S second
#define IOS cin.tie(0),ios_base::sync_with_stdio(false)
#define f2(x) ((x)*(x))

const int maxn=3e5+3,inf=1ll<<60,bl=2e9+3;
struct C{int x,y,r,id;}a[maxn];
int n,res[maxn];
bitset<maxn>rmv;
unordered_map<int,vector<int>>mp;
 
main(){
	IOS;
	cin>>n;
	int mnx=inf,mny=inf;
	REP(i,0,n)cin>>a[i].x>>a[i].y>>a[i].r,a[i].id=i,mnx=min(mnx,a[i].x),mny=min(mny,a[i].y);
	REP(i,0,n)a[i].x=a[i].x-mnx+1,a[i].y=a[i].y-mny+1;
	stable_sort(a,a+n,[](C&x,C&y){return x.r>y.r;});
	int k=inf;
	REP(i,0,n){
		if(rmv[i])continue;
		if(2*a[i].r<k){
			k=a[i].r;
			mp.clear();
			REP(j,i,n)if(!rmv[j])mp[a[j].x/k*bl+a[j].y/k].pb(j);
		}
		int xx=a[i].x/k,yy=a[i].y/k;
		REP(x,xx-2,xx+3)REP(y,yy-2,yy+3){
			auto&tls=mp[x*bl+y];
			for(auto it=tls.begin();it!=tls.end();++it){
				if(!rmv[*it]&&f2(a[i].x-a[*it].x)+f2(a[i].y-a[*it].y)<=f2(a[i].r+a[*it].r)){
					res[a[*it].id]=a[i].id;
					rmv[*it]=1;
				}
			}
		}
	}
	REP(i,0,n)cout<<res[i]+1<<" ";
}

Compilation message

circle_selection.cpp:18:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from circle_selection.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = C*; _Value = const C; _Compare = main()::<lambda(C&, C&)>]':
/usr/include/c++/7/bits/stl_algobase.h:959:14:   required from '_ForwardIterator std::__lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = C*; _Tp = C; _Compare = __gnu_cxx::__ops::_Iter_comp_val<main()::<lambda(C&, C&)> >]'
/usr/include/c++/7/bits/stl_algo.h:2501:26:   required from 'void std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance, _Compare) [with _BidirectionalIterator = C*; _Distance = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(C&, C&)> >]'
/usr/include/c++/7/bits/stl_algo.h:2772:34:   required from 'void std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = C*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(C&, C&)> >]'
/usr/include/c++/7/bits/stl_algo.h:5006:28:   required from 'void std::__stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = C*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(C&, C&)> >]'
/usr/include/c++/7/bits/stl_algo.h:5077:36:   required from 'void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter = C*; _Compare = main()::<lambda(C&, C&)>]'
circle_selection.cpp:24:48:   required from here
/usr/include/c++/7/bits/predefined_ops.h:177:11: error: no match for call to '(main()::<lambda(C&, C&)>) (C&, const C&)'
  { return bool(_M_comp(*__it, __val)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h:177:11: note: candidate: bool (*)(C&, C&) <conversion>
/usr/include/c++/7/bits/predefined_ops.h:177:11: note:   conversion of argument 3 would be ill-formed:
/usr/include/c++/7/bits/predefined_ops.h:177:11: error: binding reference of type 'C&' to 'const C' discards qualifiers
circle_selection.cpp:24:30: note: candidate: main()::<lambda(C&, C&)> <near match>
  stable_sort(a,a+n,[](C&x,C&y){return x.r>y.r;});
                              ^
circle_selection.cpp:24:30: note:   conversion of argument 2 would be ill-formed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from circle_selection.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:177:11: error: binding reference of type 'C&' to 'const C' discards qualifiers
  { return bool(_M_comp(*__it, __val)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = const C; _Iterator = C*; _Compare = main()::<lambda(C&, C&)>]':
/usr/include/c++/7/bits/stl_algo.h:2052:14:   required from '_ForwardIterator std::__upper_bound(_ForwardIterator, _ForwardIterator, const _Tp&, _Compare) [with _ForwardIterator = C*; _Tp = C; _Compare = __gnu_cxx::__ops::_Val_comp_iter<main()::<lambda(C&, C&)> >]'
/usr/include/c++/7/bits/stl_algo.h:2510:26:   required from 'void std::__merge_without_buffer(_BidirectionalIterator, _BidirectionalIterator, _BidirectionalIterator, _Distance, _Distance, _Compare) [with _BidirectionalIterator = C*; _Distance = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(C&, C&)> >]'
/usr/include/c++/7/bits/stl_algo.h:2772:34:   required from 'void std::__inplace_stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = C*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(C&, C&)> >]'
/usr/include/c++/7/bits/stl_algo.h:5006:28:   required from 'void std::__stable_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = C*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<main()::<lambda(C&, C&)> >]'
/usr/include/c++/7/bits/stl_algo.h:5077:36:   required from 'void std::stable_sort(_RAIter, _RAIter, _Compare) [with _RAIter = C*; _Compare = main()::<lambda(C&, C&)>]'
circle_selection.cpp:24:48:   required from here
/usr/include/c++/7/bits/predefined_ops.h:215:11: error: no match for call to '(main()::<lambda(C&, C&)>) (const C&, C&)'
  { return bool(_M_comp(__val, *__it)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h:215:11: note: candidate: bool (*)(C&, C&) <conversion>
/usr/include/c++/7/bits/predefined_ops.h:215:11: note:   conversion of argument 2 would be ill-formed:
/usr/include/c++/7/bits/predefined_ops.h:215:11: error: binding reference of type 'C&' to 'const C' discards qualifiers
circle_selection.cpp:24:30: note: candidate: main()::<lambda(C&, C&)> <near match>
  stable_sort(a,a+n,[](C&x,C&y){return x.r>y.r;});
                              ^
circle_selection.cpp:24:30: note:   conversion of argument 1 would be ill-formed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from circle_selection.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:215:11: error: binding reference of type 'C&' to 'const C' discards qualifiers
  { return bool(_M_comp(__val, *__it)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~