Submission #456178

#	Time	Username	Problem	Language	Result	Execution time	Memory
456178		prvocislo	Circle selection (APIO18_circle_selection)	C++17	87 / 100	3059 ms	12472 KiB

circle_selection

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

const int maxn = 3e5 + 5, logn = 30;
const ll maxi = 1e9 + 5;
struct circle { int x, y, r; };
vector<circle> c(maxn);
bool in(const int& a, const int& b)
{
    return (c[a].r + c[b].r) * 1ll * (c[a].r + c[b].r)
        >= (c[a].x - c[b].x) * 1ll * (c[a].x - c[b].x) + (c[a].y - c[b].y) * 1ll * (c[a].y - c[b].y);
}
bool cmp(const int& a, const int& b)
{
    return (c[a].r == c[b].r ? a < b : c[a].r > c[b].r);
}
vector<pair<pair<int, int>, int> > o;
vector<int> ans(maxn, -1), ord(maxn, -1);
int n, r;
inline void process(const int& i)
{
    for (int l = -2; l <= 2; l++)
    {
        int x = (c[i].x >> r) + l;
        int y1 = max(-maxi, (((ll)c[i].y) >> ((ll)r)) - (1ll << ((ll)(r + 1))));
        int y2 = min(maxi, (((ll)c[i].y) >> ((ll)r)) + (1ll << ((ll)(r + 1))));
        auto it = lower_bound(o.begin(), o.end(), make_pair(make_pair(x, y1), -1));
        while (it != o.end() && it->first <= make_pair(x, y2))
        {
            if (ans[it->second] == -1 && in(it->second, i)) ans[it->second] = i;
            it++;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> c[i].x >> c[i].y >> c[i].r;
        ord[i] = i;
    }
    sort(ord.begin(), ord.begin() + n, cmp);
    int id = 0;
    for (r = logn; r >= 0; r--)
    {
        o.clear();
        for (int i = 0; i < n; i++) if (ans[i] == -1)
            o.push_back({ {c[i].x >> r, c[i].y >> r}, i });
        sort(o.begin(), o.end());
        while (id != n && (!r || c[ord[id]].r >= (1 << (r - 1))))
        {
            if (ans[ord[id]] == -1) process(ord[id]);
            id++;
        }
    }
    for (int i = 0; i < n; i++) cout << ans[i] + 1 << " ";
    cout << "\n";
    return 0;
}

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