제출 #546765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
546765		Monarchuwu	원 고르기 (APIO18_circle_selection)	C++17	19 / 100	813 ms	41060 KiB

circle_selection

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

typedef pair<int, int> pii;
#define ff first
#define ss second

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;
        }
    }
}

namespace subtask2 {
    set<pii> s[2];
    void init() {
        for (int i = 1; i <= n; ++i) {
            s[0].emplace(a[i].x - a[i].r, i);
            s[1].emplace(a[i].x + a[i].r, i);
        }
    }
    void del(int i, int x) {
        ans[a[i].id] = x;
        s[0].erase(pii(a[i].x - a[i].r, i));
        s[1].erase(pii(a[i].x + a[i].r, i));
    }
    void solve() {
        init();
        for (int i = 1, j; i <= n; ++i) if (!ans[a[i].id]) {
            del(i, a[i].id);

            for (int b = 0; b < 2; ++b) {
                set<pii>::iterator it = s[b].lower_bound(pii(a[i].x, 0)), it2;
                while (it != s[b].end() && it->ff <= a[i].x + a[i].r) {
                    j = it->ss, ++it;
                    del(j, a[i].id);
                }

                it = s[b].lower_bound(pii(a[i].x, 0));
                if (it != s[b].begin()) {
                    --it;
                    while (it->ff >= a[i].x - a[i].r) {
                        j = it->ss;
                        bool stop = it == s[b].begin() ? true : (--it, false);
                        del(j, a[i].id);
                        if (stop) break;
                    }
                }
            }
        }
    }
}

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);

    if (n <= 5000)
        subtask1::solve();
    else
        subtask2::solve();

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

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