Submission #1095570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095570		ShadowShark	Circle selection (APIO18_circle_selection)	C++17	0 / 100	3040 ms	609160 KiB

circle_selection

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

const int maxN = 3e5 + 5;
struct circle {
    long long 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 (A.x - B.x) * (A.x - B.x) - (A.y - B.y) * (A.y - B.y) <= (A.r + B.r) * (A.r + B.r);
}

vector<int> tmp;
map<pair<long long, long long>, 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;
        long long X = curr.x / curr.r, Y = curr.y / curr.r;
        for (long long x = X - 2; x <= X + 2; x++)
            for (long long y = Y - 2; y <= Y + 2; y++) {
                if (save[{x, y}].size() == 0) continue;
                tmp.clear();
                for (auto it: save[{x, y}])
                    if (inter(C[it], curr)) ans[C[it].id] = curr.id;
                        else tmp.push_back(it);
                save[{x, y}] = tmp;
            }
    }

    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