Submission #487120

#	Time	Username	Problem	Language	Result	Execution time	Memory
487120		Redhood	Circle selection (APIO18_circle_selection)	C++14	0 / 100	3076 ms	11964 KiB

circle_selection

#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;

//const int N = (int)3e5 + 10;

//struct seg{
//    int a[4*N];
//    int p[4*N];
//    void clr(int x){
//        fill(a , a + 4 * N , x);
//        fill(p , p + 4 * N , x);
//    }
//    void push(int v){
//
//    }
//    int get(int v , int tl , int tr , int l , int r){
//        if(tl == l && tr == r){
//            return a[v];
//        }
//        int mid = (tl + tr) >> 1 , v1 = v << 1;
//        push(v);
//
//    }
//};
#define int long long
vector < array < int , 3 > > c;
bool intersec(int i , int j){
    if((__int128_t)(c[i][2] + c[j][2]) * (c[i][2] + c[j][2]) >= (__int128_t)(c[i][0]-c[j][0])*(c[i][0]-c[j][0])+
                                                                (__int128_t)(c[i][1]-c[j][1])*(c[i][1]-c[j][1])){
            return true;
    }
    return false;
}
signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;

    c.resize(n);

    for(auto &i : c)
        cin >> i[0] >> i[1] >> i[2];


    vector < int > p(n);
    iota(all(p) , 0);


    sort(all(p) , [&](int i , int j){
            if(c[i][2] == c[j][2]){
                return i < j;
         }
            return c[i][2] > c[j][2];
         });
    vector < int > ans(n, -1);
    for(int i = 0 ; i < n; ++i){
        int bst = -1;
        for(int j = 0 ; j < i; ++j){
            if(ans[p[j]] == -1 && intersec(p[i], p[j])){
                bst = p[j];
            }
        }
        ans[p[i]] = bst;
    }



    for(int i = 0; i < n; ++i){
        if(ans[i] == -1){
            cout << i + 1 << ' ';
        }else
            cout << ans[i] + 1 << ' ';
    }





    return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7


1 1 1
100000000 1 1 1
1


11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1



*/

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