oj.uz

Submission #698921

# Submission time Handle Problem Language Result Execution time Memory
698921 2023-02-14T19:50:11 Z vjudge1 Circle selection (APIO18_circle_selection) C++17
0 / 100
 168 ms 14856 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 14856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 149 ms 13252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -