Submission #366608

#	Time	Username	Problem	Language	Result	Execution time	Memory
366608		valerikk	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1354 ms	114936 KiB

circle_selection

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

struct Circle {
    ll x, y, r;
    int id;

    Circle() = default;
    
    Circle(ll x, ll y, ll r, int id) : x(x), y(y), r(r), id(id) {}
};

struct Point {
    ll y;
    int id;

    Point() = default;

    Point(ll y, int id) : y(y), id(id) {}
};

bool operator<(const Circle &a, const Circle &b) {
    return a.r > b.r || (a.r == b.r && a.id < b.id);
}

bool operator<(const Point &a, const Point &b) {
    return a.y < b.y;
}

template<class T>
T sqr(T x) {
    return x * x;
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<Circle> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i].x >> c[i].y >> c[i].r;
        c[i].id = i;
    }
    sort(c.begin(), c.end());

    auto intersect = [&](int i, int j)->bool {
        return sqr(c[i].x - c[j].x) + sqr(c[i].y - c[j].y) <= sqr(c[i].r + c[j].r);
    };

    ll R;
    vector<vector<Point>> points;

    vector<int> order_x(n);
    iota(order_x.begin(), order_x.end(), 0);
    sort(order_x.begin(), order_x.end(), [&](const int &i, const int &j) {
        return c[i].x < c[j].x;
    });
    vector<int> pos_x(n);
    vector<ll> sorted_x(n);
    for (int i = 0; i < n; i++) {
        pos_x[order_x[i]] = i;
        sorted_x[i] = c[order_x[i]].x;
    }

    vector<int> order_y(n);
    iota(order_y.begin(), order_y.end(), 0);
    sort(order_y.begin(), order_y.end(), [&](const int &i, const int &j) {
        return c[i].y < c[j].y;
    });
    vector<int> pos_y(n);
    vector<ll> sorted_y(n);
    for (int i = 0; i < n; i++) {
        pos_y[order_y[i]] = i;
        sorted_y[i] = c[order_y[i]].y;
    }

    vector<bool> used(n, false);

    int diff_x;
    vector<ll> scaled_x;
    vector<int> scaled_pos(n);
    auto do_rescaling = [&](ll R_) {
        R = R_;
        scaled_x.clear();
        scaled_x.push_back(sorted_x[0] / R);
        scaled_pos[order_x[0]] = 0;
        for (int i = 1; i < n; i++) {
            if (sorted_x[i] / R != scaled_x.back())
                scaled_x.push_back(sorted_x[i] / R);
            scaled_pos[order_x[i]] = (int)scaled_x.size() - 1;
        }
        diff_x = scaled_x.size();
        points.resize(diff_x);
        for (auto& v: points) 
            v.clear();
        for (int i = 0; i < n; i++) {
            if (!used[order_y[i]]) 
                points[scaled_pos[order_y[i]]].emplace_back(sorted_y[i] / R, order_y[i]);
        }
        /*for (int i = 0; i < n; i++)
            assert(scaled_x[scaled_pos[i]] == c[i].x / R);*/
        /*for (int i = 0; i < diff_x; i++) {
            for (const auto& p : points[i]) {
                if (!(scaled_x[i] == c[p.id].x / R && p.y == c[p.id].y / R)) {
                    cout << i << " " << p.y << " " << c[p.id].id + 1 << "\n";
                }
            }
        }
        cout << endl;*/
    };

    vector<int> answer(n, -2);
    
    do_rescaling(c[0].r);

    for (int i = 0; i < n; i++) {
        if (2 * c[i].r <= R)
            do_rescaling(c[i].r);
        if (used[i])
            continue;
       
        int left_x = lower_bound(scaled_x.begin(), scaled_x.end(), scaled_x[scaled_pos[i]] - 2) - scaled_x.begin();
        int right_x = upper_bound(scaled_x.begin(), scaled_x.end(), scaled_x[scaled_pos[i]] + 2) - scaled_x.begin();
        for (int x = left_x; x < right_x; x++) {
            int left_y = lower_bound(points[x].begin(), points[x].end(), Point{c[i].y / R - 2, -1}) - points[x].begin();
            int right_y = upper_bound(points[x].begin(), points[x].end(), Point{c[i].y / R + 2, -1}) - points[x].begin();
            for (int y = left_y; y < right_y; y++) {
                if (!used[points[x][y].id] && intersect(i, points[x][y].id)) {
                    used[points[x][y].id] = true;
                    answer[c[points[x][y].id].id] = c[i].id;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) 
        cout << answer[i] + 1 << " ";
    cout << endl;
    return 0;
}

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