Submission #698921

#	Time	Username	Problem	Language	Result	Execution time	Memory
698921		vjudge1	Circle selection (APIO18_circle_selection)	C++17	0 / 100	168 ms	14856 KiB

circle_selection

#include <bits/stdc++.h>
///#include <fstream>
#define endl '\n'
#define mod 998244353
#define INF 100000000000000
#define ll long long
///#define cin fin
///#define cout fout
#define fi first
#define se second
using namespace std;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
bool cmp(pair<pair<long long, int>,pair<long long, long long>> a, pair<pair<long long, int>,pair<long long, long long>> b) {
    if(a.fi.fi != b.fi.fi) return a.fi.fi > b.fi.fi;
    else return a.fi.se < b.fi.se;
}
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n; cin >> n; pair<pair<long long, int>,pair<long long, long long>> arr[n]; int ans[n];
    for(int i = 0; i < n; i++) ans[i] = i;
    for(int i = 0; i < n; i++) {
        long long x, y, r; cin >> x >> y >> r;
        arr[i].fi.fi = r; arr[i].fi.se = i;
        arr[i].se.fi = x; arr[i].se.se = y;
    }
    sort(arr,arr+n,cmp);

    for(int i = 0; i < n; i++) {
        if(ans[arr[i].fi.se] != arr[i].fi.se) continue;

        for(int j = i+1; j < n; j++) {
            if(ans[arr[j].fi.se] != arr[j].fi.se) continue;
            long long x1 = arr[i].se.fi, y1 = arr[i].se.se, r1 = arr[i].fi.fi;
            long long x2 = arr[j].se.fi, y2 = arr[j].se.se, r2 = arr[j].fi.fi;
            if( ((r1+r2)*(r1+r2))*((r1+r2)*(r1+r2)) >= ((abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2))*(abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2)))) {
                    ans[arr[j].fi.se] = arr[i].fi.se;

            }
        }
    }
    for(int i = 0; i < n; i++) cout << ans[i]+1 << ' ';
    return 0;
}
/*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*/

















   /* int n; cin >> n; long long arr[n]; vector<pair<pair<int,long long>,int>> v; long long ans[n];
    for(int i = 0; i < n; i++) ans[i] = i+1;
    for(int i = 0; i < n; i++) {
        long long x, y, r; cin >> x >> y >> r; arr[i] = r;
        v.push_back({{1,x-r},i});
        v.push_back({{2,x+r},i});
    }
    sort(v.begin(),v.end()); priority_queue<pair<long long, long long>> pq;
    for(int i = 0; i < v.size(); i++) {
        int ind = v[i].second;
        pq.push({arr[ind],-ind});
        if(!pq.empty() &&)
    }*/

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