Submission #698773

#	Time	Username	Problem	Language	Result	Execution time	Memory
698773		vjudge1	Circle selection (APIO18_circle_selection)	C++17	0 / 100	143 ms	11392 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+1;
    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[i] != i+1) continue;
        for(int j = i+1; j < n; j++) {
            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((y1+r1 == y2-r2 || y1-r1 == y2+r2) && x1 == x2) {
                ans[j] = i+1;
            }
            else if(y1 == y2 && (x1+r1 == x2-r2 || x1-r1 == x2+r2)) {
                ans[j] = i+1;
            }
            else if(y1-r1 < y2+r2 && x1+r1 > x2-r2) {
                ans[j] = i+1;
            }
            else if(y1+r1 > y2-r2 && x1-r1 < x2+r2) {
                ans[j] = i+1;
            }
            else if(y1-r1 < y2+r2 && x1-r1 < x2+r2) {
                ans[j] = i+1;
            }
            else if(y1+r1 > y2-r2 && x1+r1 > x2-r2) {
                ans[j] = i+1;
            }
        }
    }
    for(int i = 0; i < n; i++) cout << ans[i] << ' ';
   /* 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() &&)
    }*/
    return 0;
}

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