Submission #508208

#TimeUsernameProblemLanguageResultExecution timeMemory
508208oneloveforeverCircle selection (APIO18_circle_selection)C++14
0 / 100
947 ms42260 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define sz(x) x.size() const int N = 3e5 + 1; const int inf = 1e9 + 7; typedef vector<int> vi; struct Circle { int x, y; int R, i; int ans; } C[N]; bool Share(Circle a,Circle b) { double need=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); return need<=a.R+b.R; } ll encode(int x,int y) { return ((ll)x << 31) + y; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i = 0 ; i < n ; ++i) { cin >> C[i].x; C[i].x += inf; cin >> C[i].y; C[i].y += inf; cin >> C[i].R; C[i].i = i; C[i].ans = -1; } sort(C,C + n,[&](Circle C1,Circle C2) { if (C1.R != C2.R) return C1.R > C2.R; if (C1.R == C2.R) return C1.i < C2.i; }); int unit = 2e9 + 1; unordered_map<ll,vi> Combi; auto build = [&]() { Combi.clear(); for(int i = 0 ; i < n ; ++i) if (C[i].ans < 0) { int x = C[i].x / unit; int y = C[i].y / unit; Combi[encode(x,y)].pb(i); } }; for(int i = 0 ; i < n ; ++i) if (C[i].ans < 0) { //cout << C[i].i << " "; if (unit > C[i].R * 2) { unit = C[i].R; build(); } int x = C[i].x / unit; int y = C[i].y / unit; for(int a = x - 2 ; a < x + 3 ; ++a) for(int b = y - 2 ; b < y + 3 ; ++b) { ll Hash = encode(a,b); if(!Combi.count(Hash)) continue; vi &v = Combi[Hash]; for(int j = 0 ; j < v.size() ; ++j) if (Share(C[i],C[v[j]])) { C[v[j]].ans = C[i].i; swap(v[j],v.back()); v.pop_back(); j--; } } } sort(C,C + n,[&](Circle C1,Circle C2) { return C1.i < C2.i; }); for(int i = 0 ; i < n ; ++i) cout << C[i].ans + 1 << " "; }

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:76:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(int j = 0 ; j < v.size() ; ++j) if (Share(C[i],C[v[j]]))    {
      |                             ~~^~~~~~~~~~
circle_selection.cpp: In lambda function:
circle_selection.cpp:43:5: warning: control reaches end of non-void function [-Wreturn-type]
   43 |     });
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...