Submission #742934

#	Time	Username	Problem	Language	Result	Execution time	Memory
742934		PixelCat	Circle selection (APIO18_circle_selection)	C++14	7 / 100	124 ms	27360 KiB

circle_selection

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 5010;

int gg[MAXN];

int dist2(pii a, pii b) {
    return (a.F - b.F) * (a.F - b.F) + (a.S - b.S) * (a.S - b.S);
}

struct Circ {
    int id, x, y, r;
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // =^-w-^= nya
    int n; cin >> n;
    vector<Circ> v(n);
    For(i, 0, n - 1) {
        v[i].id = i + 1;
        cin >> v[i].x >> v[i].y >> v[i].r;
    }
    sort(all(v), [&](const Circ &a, const Circ &b) {
        if(a.r != b.r) return a.r > b.r;
        return a.id < b.id;
    });
    for(auto &c:v) {
        if(gg[c.id]) continue;
        for(auto &c2:v) if(!gg[c2.id]) {
            if(dist2(pii(c.x, c.y), pii(c2.x, c2.y)) <= (c.r + c2.r) * (c.r + c2.r)) {
                gg[c2.id] = c.id;
            }
        }
    }
    For(i, 1, n) cout << gg[i] << " \n"[i == n];
    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

*/

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