Submission #1087259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087259		TrungNotChung	Circle selection (APIO18_circle_selection)	C++11	100 / 100	1360 ms	49416 KiB

circle_selection

#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define task "main"

using namespace std;
const int N = (int)3e5 + 10; 

struct Circle {
    int x, y, r, i;
    Circle(int _x = 0, int _y = 0, int _r = 0, int _i = 0) {
        x = _x, y = _y, r = _r, i = _i;
    }
} circles[N];

int n;
int res[N];
 
bool cmp(const Circle &a, const Circle &b){
    if (a.r == b.r) return a.i < b.i;
    return a.r > b.r;
}

bool intersect(const Circle &a, const Circle &b) {
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y) <= 1LL * (a.r + b.r) * (a.r + b.r);
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> circles[i].x >> circles[i].y >> circles[i].r;
        circles[i].i = i;
    }
    sort (circles, circles + n, cmp);

    memset(res, -1, sizeof res);
    for (int lg = 30; lg >= 0; --lg) {
        int r = (1 << lg);
        map<pii, vector<int> > grid;
        bool found = false;
        for (int i = 0; i < n; ++i) {
            if (res[circles[i].i] == -1 && circles[i].r >= r / 2 && circles[i].r <= r) {
                found = true;
                break;
            }
        }
        if(!found) continue;
        for (int i = 0; i < n; ++i) {
            if (res[circles[i].i] == -1) {
                grid[pii(circles[i].x / r, circles[i].y / r)].push_back(i);
            }
        }
        for (int i = 0; i < n; ++i) {
            Circle &cur = circles[i];
            if (cur.r < r / 2) break;
            if (res[cur.i] != -1 || cur.r > r) continue;
            for(int x = cur.x / r - 2; x <= cur.x / r + 2; ++x) {
                for(int y = cur.y / r - 2; y <= cur.y / r + 2; ++y) {
                    if (grid.find(pii(x, y)) == grid.end()) continue;
                    vector<int> &candidates = grid[pii(x, y)];
                    for (int i = (int)candidates.size() - 1; i >= 0; --i) {
                        int c = candidates[i];
                        if (res[circles[c].i] == -1 && intersect(circles[c], cur)) {
                            res[circles[c].i] = cur.i;
                            swap (candidates[i], candidates.back());
                            candidates.pop_back();
                        }
                    }
                }
            }
        }
    }

    for(int i = 0; i < n; i++) cout << res[i] + 1 << ' ';
}
 
int main() {
#ifdef LOCAL
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    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