oj.uz

답안 #771915

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771915 2023-07-03T11:51:12 Z mcdx9524 원 고르기 (APIO18_circle_selection) C++17
0 / 100
 367 ms 45976 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

vector <vector <circle> > build_matrix(vector <circle> circles, int sz) {
    sort(circles.begin(), circles.end(), [](const circle &a, const circle &b) {
        return a.x < b.x; 
    });
    int n = (int) circles.size();
    vector <circle> cur;
    vector <vector <circle> > res;
    for (int i = 0; i < n; i++) {
        if (cur.empty() || cur.back().x / sz == circles[i].x / sz) {
            cur.push_back(circles[i]);
        } else {
            res.push_back(cur);
            cur = {circles[i]};
        }
    }   
    if (!cur.empty()) {
        res.push_back(cur);
    }
    for (auto &to : res) {
        sort(to.begin(), to.end(), [](const circle &a, const circle &b) {
            return a.y < b.y;
        });
    }
    return res;
}

bool query(const circle &a, const circle &b) {
    long long distance = (a.x - b.x) * 1ll * (a.x - b.x) + (a.y - b.y) * 1ll * (a.y - b.y);
    return distance <= (a.r + b.r) * 1ll * (a.r + b.r);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <circle> c;
    set <pair <int, int>, greater <pair <int, int> > > rads;
    for (int i = 0; i < n; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        c.push_back({x, y, r, i});
        rads.insert({r, -i});
    }
    int sz = rads.begin()->first;
    auto result = build_matrix(c, sz);
    vector <int> rem(n, -1);
    for (int i = 0; i < n; i++) {
        auto it = rads.begin();
        int index = -it->second;
        int cur_rad = it->first;
        rads.erase(it);
        if (rem[index] != -1) {
            continue;
        }
        rem[index] = index;
        if (cur_rad <= sz / 2) {
            sz /= 2;
            result = build_matrix(c, sz);
        }
        int xl = n, xr = -1;
        {
            int starting_point = (c[index].x / sz) * sz;
            int prev_point = starting_point - 2 * sz;
            int l = 0, r = (int) result.size() - 1;
            int res = n;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (result[mid][0].x >= prev_point) {
                    r = mid - 1;
                    res = mid;
                } else {
                    l = mid + 1;
                }
            }
            xl = res;
        }
        {
            int starting_point = (c[index].x / sz) * sz;
            int next_point = starting_point + 3 * sz;
            int l = 0, r = (int) result.size() - 1;
            int res = n;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (result[mid][0].x >= next_point) {
                    r = mid - 1;
                    res = mid;
                } else {
                    l = mid + 1;
                }
            }
            xr = res;
            xr--;
        }
        xl = max(0, xl);
        xr = min((int) result.size() - 1, xr);
        for (int j = xl; j <= xr; j++) {
            int yl = n, yr = -1;
            {
                int starting_point = (c[index].y / sz) * sz;
                int prev_point = starting_point - 2 * sz;
                int l = 0, r = (int) result[j].size() - 1;
                int res = n;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (result[j][mid].y >= prev_point) {
                        r = mid - 1;
                        res = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                yl = res;
            }
            {
                int starting_point = (c[index].y / sz) * sz;
                int next_point = starting_point + 3 * sz;
                int l = 0, r = (int) result[j].size() - 1;
                int res = n;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (result[j][mid].y >= next_point) {
                        r = mid - 1;
                        res = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                yr = res;
                yr--;
            }
            yl = max(0, yl);
            yr = min((int) result[j].size() - 1, yr);
            for (int k = yl; k <= yr; k++) {
                if (rem[result[j][k].index] == -1 && query(c[index], result[j][k])) {
                    rem[result[j][k].index] = index;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << rem[i] + 1 << ' ';
    }
    cout << '\n';
    return 0;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 40816 KB Output is correct
2 Correct 287 ms 45260 KB Output is correct
3 Correct 270 ms 40392 KB Output is correct
4 Incorrect 358 ms 45976 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 367 ms 24800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 322 ms 31996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -