oj.uz

Submission #1095570

# Submission time Handle Problem Language Result Execution time Memory
1095570 2024-10-02T14:58:41 Z ShadowShark Circle selection (APIO18_circle_selection) C++17
0 / 100
 3000 ms 609160 KB 
#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.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 609160 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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

Subtask #6
0 / 13.0

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