Submission #261002

#	Time	Username	Problem	Language	Result	Execution time	Memory
261002		SorahISA	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3075 ms	26328 KiB

circle_selection

#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)

const int INF = 0x7f7f7f7f;
const int maxn = 3E5 + 5;

struct Circle {
    int x, y, r, id;
    bool operator < (const Circle &rhs) const {
        if (r == rhs.r) return id > rhs.id;
        return r < rhs.r;
    }
};

int32_t main() {
    fastIO();
    
    int n;
    cin >> n;
    
    Prior<Circle> pq;
    vector<Circle> cir(n);
    for (int i = 0; i < n; ++i) {
        cin >> cir[i].x >> cir[i].y >> cir[i].r;
        cir[i].id = i;
        pq.push(cir[i]);
    }
    
    vector<int> ans(n, -1);
    for (int i = 0; i < n; ++i) {
        while (!pq.empty() and ans[pq.top().id] != -1) pq.pop();
        for (int j = 0; j < n; ++j) {
            if (ans[j] != -1) continue;
            int dx = abs(cir[pq.top().id].x - cir[j].x);
            int dy = abs(cir[pq.top().id].y - cir[j].y);
            int dr =     cir[pq.top().id].r + cir[j].r;
            // cout << dx << " " << dy << " " << dr << "\n";
            if (dx*dx + dy*dy <= dr*dr) ans[j] = pq.top().id;
        }
    }
    
    for (int i = 0; i < n; ++i) cout << ans[i] + 1 << " \n"[i == n-1];
    
    return 0;
}

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