Submission #87150

#	Time	Username	Problem	Language	Result	Execution time	Memory
87150		fedoseevtimofey	Circle selection (APIO18_circle_selection)	C++14	7 / 100	3033 ms	59608 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector <int> x(n), y(n), r(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i] >> r[i];
    vector <int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    vector <int> who(n, -1);
    sort(idx.begin(), idx.end(), [&] (int i, int j) {
        if (r[i] != r[j]) return r[i] > r[j];
        return i < j;
    });
    for (int i : idx) {
        if (who[i] != -1) continue;
        who[i] = i + 1;
        for (int j = 0; j < n; ++j) {
            if (who[j] == -1 && (ll)(x[i] - x[j]) * (x[i] - x[j]) + (ll)(y[i] - y[j]) * (y[i] - y[j]) <= (ll)(r[i] + r[j]) * (r[i] + r[j])) {
                who[j] = i + 1;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << who[i] << ' ';
    }
}

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