Submission #698932

#TimeUsernameProblemLanguageResultExecution timeMemory
698932vjudge1Circle selection (APIO18_circle_selection)C++17
0 / 100
3008 ms65260 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' const int M = 3e5+5, MOD = 1e9; struct circle {int x, y, r, i;}; struct event {int t, x, y, i;}; bool operator<(circle a, circle b) {if (a.r == b.r) return a.i < b.i; return a.r > b.r;}; bool operator<(event a, event b) {return (a.t == b.t? (a.i%3 == b.i%3?a.i/3 > b.i/3: a.i%3 < b.i%3) : a.t < b.t);} int p[M]; int sq(int a) {return a*a;} int dist(int x1, int y1, int x2, int y2) { return sq(x1-x2) + sq(y1-y2); } int cnt; vector<circle> dnc(vector<circle> v) { if (v.size() <= 1) return v; vector<circle> a, b; int n = v.size(), m = n/2; for (int i = 0; i < m; i++) a.push_back(v[i]); for (int i = m; i < n; i++) b.push_back(v[i]); int tmp = ++cnt; a = dnc(a); multiset<event> timeline; for (auto [x, y, r, i]:b) timeline.insert({x-r, x, y, 3*i + 1}), timeline.insert({x+r, x, y, 3*i + 1}); for (auto [x, y, r, i]:a) timeline.insert({x-r, x, y, 3*i}), timeline.insert({x+r, x, y, 3*i + 2}); vector<circle> end; multiset<circle> st; for (auto [t, x, y, i]:timeline) { if (i%3 == 0) st.insert({x, y, x-t, i/3}); if (i%3 == 1) { i /= 3; int r = abs(t-x); for (auto [x2, y2, r2, i2]:st) if (dist(x, y, x2, y2) <= sq(r + r2)) p[i] = max(p[i], i2); if (!p[i] && t > x) end.push_back({x, y, r, i}); } // if (i%3 == 2) st.erase(st.find({x, y, t-x, i/3})); } end = dnc(end); for (auto i:a) end.push_back(i); return end; } signed main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<circle> v; for (int i = 1; i <= n; i++) { int x, y, r; cin >> x >> y >> r; v.push_back({x, y, r, i}); } sort(v.begin(), v.end()); for (auto [a, b, c, i]:v) cout << i << ' '; cout << endl; for (auto [a, b, c, i]:dnc(v)) p[i] = i; // dnc(v); for (int i = 1; i <= n; i++) cout << p[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 ------- 7 0 0 2 -1 0 1 0 0 1 1 0 1 10 0 5 11 0 5 50 0 1 ------- 7 1 3 4 8 10 2 5 6 9 11 */

Compilation message (stderr)

circle_selection.cpp: In function 'std::vector<circle> dnc(std::vector<circle>)':
circle_selection.cpp:28:9: warning: unused variable 'tmp' [-Wunused-variable]
   28 |     int tmp = ++cnt;
      |         ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:69:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   69 |     for (auto [a, b, c, i]:v) cout << i << ' '; cout << endl;
      |     ^~~
circle_selection.cpp:69:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |     for (auto [a, b, c, i]:v) cout << i << ' '; cout << endl;
      |                                                 ^~~~
circle_selection.cpp:74:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   74 |     for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
      |     ^~~
circle_selection.cpp:74:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   74 |     for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
      |                                                       ^~~~
#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...