Submission #1105430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105430		sqwiijqk	Circle selection (APIO18_circle_selection)	C++17	100 / 100	1642 ms	49480 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int qwerty = 1;
    // cin >> qwerty;
    while (qwerty--) {
        solve();
    }
}

struct circle {
    int x, y, r, ind;
};

bool cmp(circle a, circle b) {
    return a.r > b.r || (a.r == b.r && a.ind < b.ind);
}

bool per(circle a, 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() {
    int n;
    cin >> n;
    vector<circle> cs(n);
    for (int i = 0; i < n; i++) {
        cin >> cs[i].x >> cs[i].y >> cs[i].r;
        cs[i].ind = i;
    }
    sort(cs.begin(), cs.end(), cmp);
    vector<int> ans(n, -1);
    for (int for_r = 30; for_r >= 0; for_r--) {
        int r = (1 << for_r);
        map<pair<int, int>, vector<int>> mp;
        bool flag = false;
        for (int i = 0; i < n; ++i) {
            if (ans[cs[i].ind] == -1 && cs[i].r >= r / 2 && cs[i].r <= r) {
                flag = true;
                break;
            }
        }
        if (!flag) continue;
        for (int i = 0; i < n; i++) {
            if (ans[cs[i].ind] == -1) {
                mp[{cs[i].x / r, cs[i].y / r}].push_back(i);
            }
        }
        for (int i = 0; i < n; i++) {
            if (cs[i].r < r / 2) break;
            if (cs[i].r > r || ans[cs[i].ind] != -1) continue;
            for (int x = cs[i].x / r - 2; x <= cs[i].x / r + 2; x++) {
                for (int y = cs[i].y / r - 2; y <= cs[i].y / r + 2; y++) {
                    if (mp.find({x, y}) == mp.end()) continue;
                    vector<int> &now = mp[{x, y}];
                    for (int j = (int) now.size() - 1; j >= 0; j--) {
                        int jj = now[j];
                        if (per(cs[i], cs[jj])) {
                            ans[cs[jj].ind] = cs[i].ind;
                            swap(now[j], now.back());
                            now.pop_back();
                        }
                    }
                }
            }
        }
    }
    for (int i: ans) {
        cout << i + 1 << ' ';
    }
}

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