Submission #698738

#	Time	Username	Problem	Language	Result	Execution time	Memory
698738		vjudge1	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3079 ms	77552 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], l[M], r[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;

    int mx = INT_MIN;
    set<circle> v;
    set<pair<int, int>> rng;
    for (int i = 1; i <= n; i++) {
        int x, y, r_;
        cin >> x >> y >> r_;

        l[i] = x-r_;
        r[i] = x+r_;
        mx = max(mx, y);
        rng.insert({l[i], i});
        rng.insert({r[i], i});
        v.insert({x, y, r_, i});
    }

    if (mx) {
        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);
        }
    } else {
        vector<int> ind;
        for (int i = 1; i <= n; i++) ind.push_back(i);
        sort(ind.begin(), ind.end(), [](int a, int b) {if (r[a]-l[a] == r[b]-l[b]) return a < b; return r[a]-l[a] > r[b]-l[b];});
        for (int a:ind) {
            if (rng.find({l[a], a}) == rng.end()) continue;
            p[a] = a;
            auto end = rng.find({r[a], a});
            while (true) {
                auto nxt = rng.upper_bound({l[a], a});
                if (nxt == end) break;
                // cout << l[nxt->second] << ',' << r[nxt->second] << ' ' << nxt->second << endl;
                // for (auto [a, b]:rng) cout <<"{"<< a << ", " << b << "}, "; cout << endl;
                p[nxt->second] = a;
                rng.erase({l[nxt->second], nxt->second});
                rng.erase({r[nxt->second], nxt->second});
                
            }

            auto begin = rng.lower_bound({l[a], a});
            rng.erase(begin);
            rng.erase(end);
        }
    }

    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
-------
*/

Compilation message (stderr)

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