Submission #399800

#TimeUsernameProblemLanguageResultExecution timeMemory
399800my99nCircle selection (APIO18_circle_selection)C++14
0 / 100
301 ms22328 KiB
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<long long,long long> point; struct A { long long x, y, r; int i; bool operator < (const A & o) const { if (x == o.x) return i < o.i; return x < o.x; } }; A cir[300100]; A s[300100]; bool compare (A & a, A & b) { if (a.r == b.r) return a.i < b.i; return a.r > b.r; } int ans[300100]; long long dis (point i, point j) { long long temp = ((i.x-j.x) * (i.x-j.x)) + ((i.y-j.y) * (i.y-j.y)); return temp; } bool intersect (A i, A j) { // cerr << dis({i.x, i.y}, {j.x, j.y}) << ' ' << (i.r+j.r) << endl; return (dis({i.x, i.y}, {j.x, j.y}) <= (i.r+j.r)*(i.r+j.r)); } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for (int i = 1; i <= n; i++) { long long x, y, r; cin >> x >> y >> r; cir[i] = {x, y, r, i}; s[i] = {x, y, r, i}; } sort(cir+1, cir+1+n, compare); // cerr << "here" << endl; // for (int i = 1; i <= n; i++) { // auto a = s.lower_bound(cir[i]); // assert(a->i == cir[i].i); // } sort(s+1, s+1+n); for (int i = 1; i <= n; i++) { int ind = cir[i].i; if (ans[ind]) continue; int a = lower_bound(s+1, s+1+n, cir[i]) - s; assert(s[a].i == cir[i].i); // cerr << a->i << endl; for (int j = a; j > 0; j--) { if (s[j].i == -1) continue; if (!intersect(s[j], cir[i])) break; ans[s[j].i] = ind; s[j].i = -1; } for (int j = a+1; j <= n; j++) { if (s[j].i == -1) continue; if (!intersect(s[j], cir[i])) break; ans[s[j].i] = ind; s[j].i = -1; } } for (int i = 1; i <= n; i++) { cout << ans[i] << ' '; } cout << endl; return 0; } /* 11 9 9 2 13 2 1 11 8 2 3 3 2 3 12 1 12 14 1 9 8 5 2 8 2 5 2 1 14 4 2 14 14 1 */
#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...