Submission #546754

#	Time	Username	Problem	Language	Result	Execution time	Memory
546754		Monarchuwu	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3057 ms	14960 KiB

circle_selection

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N = 3e5 + 7;
int n;
int ans[N];
struct Data {
    int x, y, r, id;
    Data() {}
    bool operator < (const Data &o) const {
        if (r != o.r) return r > o.r;
        return id < o.id;
    }
} a[N];

namespace subtask1 {
#define sqr(x) (ll)(x) * (x)
    bool check(const Data &a, const Data &b) {
        return sqr(a.r + b.r) >= sqr(a.x - b.x) + sqr(a.y - b.y);
    }
#undef sqr
    void solve() {
        for (int i = 1; i <= n; ++i) if (!ans[a[i].id]) {
            ans[a[i].id] = a[i].id;
            for (int j = i + 1; j <= n; ++j)
                if (!ans[a[j].id] && check(a[i], a[j])) ans[a[j].id] = a[i].id;
        }
    }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].x >> a[i].y >> a[i].r, a[i].id = i;
    sort(a + 1, a + n + 1);

    subtask1::solve();
    for (int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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