Submission #569939

#	Time	Username	Problem	Language	Result	Execution time	Memory
569939		UfoTanShin	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3064 ms	14188 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
typedef deque<int> di;
typedef deque<pi> dpi;
typedef deque<bool> db;
typedef vector<ll> vi;
typedef vector<pi> vpi;
typedef vector<bool> vb;

#define NO cout << "NO" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define Yes cout << "Yes" << endl
#define endl '\n'
const ll INF = 1e9;
const int MOD = 1e9+7;
const int MAXN = 2e5;

struct circle{
    ll r,ind,x,y;
};

bool compare(circle a, circle b){
    if (a.r != b.r){
        return a.r < b.r;
    }
    return a.ind < b.ind;
}

void solve()
{
    ll n;
    cin >> n;
    vector<circle>v(n);
    for (ll i = 0; i < n; i++){
        ll x,y,r;
        cin >> x >> y >> r;
        v[i].x = x;
        v[i].y = y;
        v[i].ind = i;
        v[i].r = r;
    }
    sort(all(v),compare);
    /* for (int i = 0; i < n; i++){
        cout << v[i].r << " ";
    } */
    vector<ll>rec(n,-1);
    for(ll i = n-1; i >= 0; i--){
        if(rec[v[i].ind] == -1){
            rec[v[i].ind] = v[i].ind+1;
            //int cnt = 0;
            for (int j = 0; j < n; j++){
                if (rec[v[j].ind] == -1 && (abs(v[j].x-v[i].x)*abs(v[j].x-v[i].x))+(abs(v[j].y-v[i].y)*abs(v[j].y-v[i].y)) 
                <= (v[j].r+v[i].r)*(v[j].r+v[i].r)){
                    rec[v[j].ind] = v[i].ind+1;
                    //cnt++;
                }
            }
            //cout <<"i: " << i << " cnt: " << cnt << endl;
        }
    }
    /* vi ans(n);
    for (int i = 0; i < n; i++){
        ans[v[i].ind] = rec[i];
    } */
    for (int i = 0; i < n; i++){
        cout << rec[i] << " ";
    }
    
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
}

//To input a whole line without getting seperated by spaces, use getline(cin, string_name)
//Make string to int: stoi(your_String)
//Make int to string: to_string(your_Int)

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