Submission #988465

#	Time	Username	Problem	Language	Result	Execution time	Memory
988465		876pol	Circle selection (APIO18_circle_selection)	C++17	7 / 100	3031 ms	15188 KiB

circle_selection

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = int;
using pll = pair<ll, ll>;
template <class T>
using vec = vector<T>;
template <class T>
using indexed_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define FOR(i, s, e) for (ll i = (ll)s; i < e; i++)
#define CFOR(i, s, e) for (ll i = (ll)s; i <= e; i++)
#define TRAV(e, a) for (const auto &e : a)
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl;

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &out, const T &obj) {
    out << "[";
    for (auto it = obj.begin(); it != obj.end(); it++) {
        out << &", "[2 * (it == obj.begin())] << *it;
    }
    return out << "]";
}

template <class K, class V>
ostream &operator<<(ostream &out, const pair<K, V> &obj) {
    return out << "(" << obj.first << ", " << obj.second << ")";
}

struct circle {
    ll x, y, r, id;
};

ostream &operator<<(ostream &out, const circle &obj) {
    return out << vec<ll>{obj.x, obj.y, obj.r, obj.id};
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;
    vec<circle> a(n);
    FOR(i, 0, n) {
        cin >> a[i].x >> a[i].y >> a[i].r;
        a[i].id = i;
    }
    vec<bool> visited(n);
    vec<ll> ans(n);
    sort(all(a), [&](const circle &o1, const circle &o2) {
        return (o1.r == o2.r) ? o1.id < o2.id : o1.r > o2.r;
    });
    FOR(i, 0, n) {
        if (visited[a[i].id]) continue;
        ans[a[i].id] = a[i].id;
        visited[a[i].id] = 1;
        FOR(j, i + 1, n) {
            if (visited[a[j].id]) continue;
            if (pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2) <=
                pow(a[i].r + a[j].r, 2)) {
                visited[a[j].id] = 1;
                ans[a[j].id] = a[i].id;
            }
        }
    }
    FOR(i, 0, n) cout << ans[i] + 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