Submission #217568

#	Time	Username	Problem	Language	Result	Execution time	Memory
217568		VEGAnn	Circle selection (APIO18_circle_selection)	C++14	7 / 100	201 ms	1024 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010;
const int oo = 2e9;
int x[N], y[N], r[N], n, mrk[N];

ll sqr(ll x){ return (x * x);}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i] >> r[i];

    fill(mrk, mrk + n, -1);

    int kol = n;

    for (; kol > 0; ){
        int nom = -1, mx = -1;

        for (int i = 0; i < n; i++){
            if (mrk[i] >= 0) continue;

            if (r[i] > mx){
                mx = r[i];
                nom = i;
            }
        }

        for (int i = 0; i < n; i++){
            if (mrk[i] >= 0) continue;

            ll cur = sqr(x[i] - x[nom]) + sqr(y[i] - y[nom]) - sqr(r[i] + r[nom]);

            if (cur <= 0){
                mrk[i] = nom;
                kol--;
            }
        }
    }

    for (int i = 0; i < n; i++)
        cout << mrk[i] + 1 << " ";

    return 0;
}

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