Submission #698676

#	Time	Username	Problem	Language	Result	Execution time	Memory
698676		vjudge1	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3062 ms	54800 KiB

circle_selection

#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;};
bool operator<(circle a, circle b) {if (a.r == b.r) return a.i < b.i; return a.r > b.r;};
int p[M];
    
int sq(int a) {return a*a;}
int dist(circle a, circle b) {
    return sq(a.x-b.x) + sq(a.y-b.y);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;

    set<circle> v;
    for (int i = 1; i <= n; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        v.insert({x, y, r, i});
    }

    while (v.size()) {
        auto a = *v.begin();
        v.erase(v.begin());
        // cout << a.i << ": ";
        p[a.i] = a.i;

        set<circle> st;
        for (auto b:v) {
            if (dist(a, b) <= sq(a.r+b.r)) {
                p[b.i] = a.i;
                // cout << b.i << ' ';
                st.insert(b);
            }
        } //cout << endl;

        for (auto c:st) v.erase(c);
    }

    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

*/

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:48:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   48 |     for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
      |     ^~~
circle_selection.cpp:48:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   48 |     for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
      |                                                       ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13