Submission #1095564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095564		ShadowShark	Circle selection (APIO18_circle_selection)	C++17	0 / 100	3060 ms	610644 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;

const int maxN = 3e5 + 5;
struct circle {
    int x, y, r, id;

    bool operator < (const circle& rhs) const {
        if (r != rhs.r) return r > rhs.r;
        return id < rhs.id;
    }
} C[maxN];
int ans[maxN];

bool inter(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);
}

map<pair<int, int>, vector<int>> save;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> C[i].x >> C[i].y >> C[i].r;
        C[i].id = i;
    }

    sort(C + 1, C + n + 1);

    for (int i = 1; i <= n; i++) {
        C[i].x += 1e9; C[i].y += 1e9;
        save[{C[i].x / C[i].r, C[i].y / C[i].r}].push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        circle& curr = C[i];

        if (ans[curr.id]) continue;
        int X = curr.x / curr.r, Y = curr.y / curr.r;
        for (int x = X - 2; x <= X + 2; x++)
            for (int y = Y - 2; y <= Y + 2; y++) {
                if (save[{x, y}].size() == 0) continue;
                for (auto it: save[{x, y}])
                    if (!ans[C[it].id] && inter(C[it], curr)) ans[C[it].id] = curr.id;
        }
    }

    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    return 0;
}

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