Submission #563039

#	Time	Username	Problem	Language	Result	Execution time	Memory
563039		Bill_00	Circle selection (APIO18_circle_selection)	C++14	7 / 100	105 ms	15228 KiB

circle_selection

#include <bits/stdc++.h>
#define N 1000005
#define ff first
#define ss second
#define ll long long 
const ll MAXN = 1e9; 
using namespace std;

ll n;
ll x[N], y[N], r[N], ans[N];

ll dist(int i1, int i2){
    return (x[i1] - x[i2]) * (x[i1] - x[i2]) + (y[i1] - y[i2]) * (y[i1] - y[i2]);
}
void solvesubtask1(){
    set<pair<ll, ll> > s;
    for(int i = 1; i <= n; i++){
        s.insert({-r[i], i});
    }
    while(s.size()){
        int k = s.begin() -> ss;
        for(int i = 1; i <= n; i++){
            if(ans[i] == 0){
                if(dist(i, k) <= ((r[i] + r[k]) * (r[i] + r[k]))){
                    ans[i] = k;
                    s.erase({-r[i], i});
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        cout << ans[i] << ' ';
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
    }
    if(n <= 5000){
        solvesubtask1();
    }

}

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