Submission #1172271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172271		benjaminkleyn	Circle selection (APIO18_circle_selection)	C++20	100 / 100	1807 ms	50932 KiB

circle_selection

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

struct Mine {
    int x, y, r, idx;
};
bool operator<(const Mine &A, const Mine &B) {
    return A.r > B.r || (A.r == B.r && A.idx < B.idx);
}
pair<int, int> find_block(const Mine &M, int block_size) {
    return {M.x / block_size, M.y / block_size};
}

int N;
vector<Mine> mines;
bool destroyed[300000];
int ans[300000];

int block_size;
map<pair<int,int>, set<int>> mines_in_block;
void compress()
{
    mines_in_block.clear();
    for (int i = 0; i < N; i++) {
        if (destroyed[i])
            continue;
        pair<int, int> block = find_block(mines[i], block_size);
        if (mines_in_block.find(block) == mines_in_block.end())
            mines_in_block[block] = set<int>();
        mines_in_block[block].insert(i);
    }
}

ll dist2(const Mine &A, const Mine &B) {
    return (A.x - B.x) * (ll) (A.x - B.x) 
         + (A.y - B.y) * (ll) (A.y - B.y);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> N;
    mines = vector<Mine>(N);
    for (int i = 0; i < N; i++) {
        cin >> mines[i].x >> mines[i].y >> mines[i].r;
        mines[i].idx = i;
    }
    sort(mines.begin(), mines.end());

    block_size = mines[0].r;
    compress();
    for (int i = 0; i < N; i++) {
        if (destroyed[i])
            continue;
        ans[mines[i].idx] = mines[i].idx;
        if (mines[i].r * 2 <= block_size) {
            block_size = mines[i].r;
            compress();
        }
        pair<int, int> block = find_block(mines[i], block_size);
        for (int block_x = block.first - 2; block_x <= block.first + 2; block_x++)
            for (int block_y = block.second - 2; block_y <= block.second + 2; block_y++) {
                if (mines_in_block.find(pair(block_x, block_y)) == mines_in_block.end())
                    continue;
                vector<int> bad;
                for (int j : mines_in_block[pair(block_x, block_y)]) {
                    if (destroyed[j]) {
                        bad.push_back(j);
                        continue;
                    }
                    if (dist2(mines[i], mines[j]) <= (mines[i].r + mines[j].r) * (ll) (mines[i].r + mines[j].r)) {
                        bad.push_back(j);
                        destroyed[j] = true;
                        ans[mines[j].idx] = mines[i].idx;
                    }
                }
                for (int j : bad)
                    mines_in_block[pair(block_x, block_y)].erase(j);
            }
    }
    for (int i = 0; i < N; i++)
        cout << ans[i]+1 << ' ';
    cout << '\n';

    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