oj.uz

Submission #561996

# Submission time Handle Problem Language Result Execution time Memory
561996 2022-05-14T03:45:51 Z KoD Circle selection (APIO18_circle_selection) C++17
0 / 100
 539 ms 18232 KB 
#include <bits/stdc++.h>

using std::array;
using std::pair;
using std::tuple;
using std::vector;

constexpr int LOG = 30;

int main() {
    int N;
    std::cin >> N;
    vector<int> X(N), Y(N), R(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i] >> R[i];
    }

    int logR = LOG;
    vector<int> xs = {0};
    vector<vector<int>> pts = {{}};
    for (int i = 0; i < N; ++i) {
        pts[0].push_back(i);
    }
    std::sort(pts[0].begin(), pts[0].end(),
              [&](const int i, const int j) { return Y[i] < Y[j]; });

    vector<int> order(N), ans(N, -1);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(),
              [&](const int i, const int j) { return R[i] != R[j] ? R[i] > R[j] : i < j; });
    for (const int i : order) {
        if (ans[i] != -1) {
            continue;
        }
        while (R[i] <= (1 << (logR - 1))) {
            logR -= 1;
            vector<int> next_xs;
            vector<vector<int>> next_pts;
            for (int i = 0; i < (int)xs.size(); ++i) {
                array<vector<int>, 2> arr;
                for (const int j : pts[i]) {
                    arr[Y[j] >> logR & 1].push_back(j);
                }
                for (int k = 0; k < 2; ++k) {
                    if (!arr[k].empty()) {
                        next_xs.push_back(xs[i] * 2 + k);
                        next_pts.push_back(std::move(arr[k]));
                    }
                }
            }
            xs = std::move(next_xs);
            pts = std::move(next_pts);
        }
        ans[i] = i;
        int xi = std::lower_bound(xs.begin(), xs.end(), (X[i] >> logR) - 2) - xs.begin();
        while (xi < (int)xs.size() && xs[xi] <= (X[i] >> logR) + 2) {
            const auto& ys = pts[xi];
            int yi = std::partition_point(ys.begin(), ys.end(),
                                          [&](const int j) { return Y[i] - Y[j] > 2 * R[i]; }) -
                     ys.begin();
            while (yi < (int)ys.size() && Y[ys[yi]] - Y[i] <= 2 * R[i]) {
                const int j = ys[yi];
                if (ans[j] == -1) {
                    const long long dx = X[i] - X[j];
                    const long long dy = Y[i] - Y[j];
                    const long long r = R[i] + R[j];
                    if (dx * dx + dy * dy <= r * r) {
                        ans[j] = i;
                    }
                }
                yi += 1;
            }
            xi += 1;
        }
    }
    for (int i = 0; i < N; ++i) {
        std::cout << ans[i] + 1 << " \n"[i + 1 == N];
    }
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 12708 KB Output is correct
2 Correct 388 ms 12852 KB Output is correct
3 Correct 362 ms 11308 KB Output is correct
4 Incorrect 387 ms 12732 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 539 ms 18232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -