Submission #981502

#	Time	Username	Problem	Language	Result	Execution time	Memory
981502		vjudge1	Circle selection (APIO18_circle_selection)	C++17	7 / 100	154 ms	35876 KiB

circle_selection

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N = 1e6 + 5, MOD = 998244353;
typedef long double ld;
ld dist(ld x,ld y,ld x1,ld y1){
    return sqrtl((x- x1) * (x - x1) + (y - y1) * (y - y1));
}
int n,p[N],res[N];
vector<array<ld,4>> a;
void test(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        ll _x,_y,_r;
        cin >> _x >> _y >> _r;
        a.push_back({(ld)_r,(ld)-i,(ld)_x,(ld)_y});
        res[i] = -1;
    }
    sort(a.rbegin(),a.rend());
    if(n <= 5000) {
        for (int j = 0; j < n; j++) {
            ld r = a[j][0], x = a[j][2], y = a[j][3];
            int i = -a[j][1];
            if(res[i] != -1) continue;
            res[i] = i;
            for (int k = j + 1; k < n; k++) {
                if (res[(int)-a[k][1]]==-1&&dist(x,y,a[k][2],a[k][3]) <= r + a[k][0]) {
                    res[(int)-a[k][1]] = i;
                }
            }
        }
    }
    for(int i = 1;i <= n;i++){
        cout << res[i] << '\n';
    }
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int T = 1;
//    cin >> T;
    while (T--){
        test();
    }
}

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