Submission #291319

#	Time	Username	Problem	Language	Result	Execution time	Memory
291319		blue	Circle selection (APIO18_circle_selection)	C++11	7 / 100	3089 ms	18916 KiB

circle_selection

#include <iostream>
#include <vector>
using namespace std;

long long sq(long long a)
{
    return a*a;
}

//7 pts: n <= 5000

int main()
{
    long long n;
    cin >> n;

    long long x[n+1], y[n+1], r[n+1];
    for(long long i = 1; i <= n; i++) cin >> x[i] >> y[i] >> r[i];

    vector<long long> kill(n+1, 0);
    long long c;
    r[0] = 0;
    while(1)
    {
        c = 0;
        for(long long i = 1; i <= n; i++) if(!kill[i] && r[i] > r[c]) c = i;
        if(!c) break;
        for(long long i = 1; i <= n; i++)
            if(!kill[i] && sq(x[i] - x[c]) + sq(y[i] - y[c]) <= sq(r[i] + r[c]))
                kill[i] = c;
    }
    for(long long i = 1; i <= n; i++) cout << kill[i] << ' ';
    cout << '\n';
}

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