oj.uz

Submission #902373

# Submission time Handle Problem Language Result Execution time Memory
902373 2024-01-10T10:33:01 Z Trisanu_Das Circle selection (APIO18_circle_selection) C++17
64 / 100
 3000 ms 476656 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int64_t, int64_t> pii;
 
const int64_t maxn = 3e5 + 3;
const int64_t inf = 1ll << 60;
const int64_t bl = 2e9 + 3;
 
struct C {
    int64_t x, y, r, id;
};
 
int64_t n, res[maxn];
bitset<maxn> rmv;
unordered_map<int64_t, vector<int64_t>> mp;
 
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cin >> n;
    C a[maxn];
    for (int64_t i = 0; i < n; ++i) cin >> a[i].x >> a[i].y >> a[i].r, a[i].id = i;
    stable_sort(a, a + n, [](const C &x, const C &y) { return x.r > y.r; });
    int64_t k = inf;
    for (int64_t i = 0; i < n; ++i) {
        if (rmv[i]) continue;
        if (2 * a[i].r < k) {
            k = a[i].r;
            mp.clear();
            for (int64_t j = i; j < n; ++j) if (!rmv[j]) mp[a[j].x / k * bl + a[j].y / k].push_back(j);
        }
 
        int64_t xx = a[i].x / k, yy = a[i].y / k;
        for (int64_t x = xx - 2; x <= xx + 2; ++x)
            for (int64_t y = yy - 2; y <= yy + 2; ++y) {
                auto &tls = mp[x * bl + y];
                for (auto it = tls.begin(); it != tls.end(); ++it) {
                    if (!rmv[*it] && (a[i].x - a[*it].x) * (a[i].x - a[*it].x) + (a[i].y - a[*it].y) * (a[i].y - a[*it].y) <= (a[i].r + a[*it].r) * (a[i].r + a[*it].r)) {
                        res[a[*it].id] = a[i].id;
                        rmv[*it] = 1;
                    }
                }
            }
    }
    for (int64_t i = 0; i < n; ++i) cout << res[i] + 1 << " ";
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 7 ms 9852 KB Output is correct
3 Correct 7 ms 9820 KB Output is correct
4 Correct 7 ms 9828 KB Output is correct
5 Correct 5 ms 9828 KB Output is correct
6 Correct 7 ms 9828 KB Output is correct
7 Correct 5 ms 9864 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 7 ms 9828 KB Output is correct
10 Correct 5 ms 9832 KB Output is correct
11 Correct 7 ms 9928 KB Output is correct
12 Correct 7 ms 9832 KB Output is correct
13 Correct 6 ms 9788 KB Output is correct
14 Correct 5 ms 9832 KB Output is correct
15 Correct 6 ms 9728 KB Output is correct
16 Correct 7 ms 9820 KB Output is correct
17 Correct 6 ms 9820 KB Output is correct
18 Correct 7 ms 9816 KB Output is correct
19 Correct 7 ms 10072 KB Output is correct
20 Correct 10 ms 10076 KB Output is correct
21 Correct 8 ms 10072 KB Output is correct
22 Correct 17 ms 13852 KB Output is correct
23 Correct 17 ms 13852 KB Output is correct
24 Correct 17 ms 13748 KB Output is correct
25 Correct 17 ms 13852 KB Output is correct
26 Correct 16 ms 13848 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 29316 KB Output is correct
2 Correct 155 ms 25228 KB Output is correct
3 Correct 128 ms 25284 KB Output is correct
4 Correct 120 ms 28924 KB Output is correct
5 Correct 132 ms 23968 KB Output is correct
6 Correct 688 ms 77228 KB Output is correct
7 Correct 148 ms 27520 KB Output is correct
8 Correct 229 ms 35988 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9816 KB Output is correct
2 Correct 754 ms 89788 KB Output is correct
3 Correct 2647 ms 260000 KB Output is correct
4 Correct 2627 ms 260680 KB Output is correct
5 Correct 2041 ms 160052 KB Output is correct
6 Correct 769 ms 89668 KB Output is correct
7 Correct 299 ms 46104 KB Output is correct
8 Correct 35 ms 19736 KB Output is correct
9 Correct 2805 ms 178716 KB Output is correct
10 Correct 1552 ms 146856 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 7 ms 9852 KB Output is correct
3 Correct 7 ms 9820 KB Output is correct
4 Correct 7 ms 9828 KB Output is correct
5 Correct 5 ms 9828 KB Output is correct
6 Correct 7 ms 9828 KB Output is correct
7 Correct 5 ms 9864 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 7 ms 9828 KB Output is correct
10 Correct 5 ms 9832 KB Output is correct
11 Correct 7 ms 9928 KB Output is correct
12 Correct 7 ms 9832 KB Output is correct
13 Correct 6 ms 9788 KB Output is correct
14 Correct 5 ms 9832 KB Output is correct
15 Correct 6 ms 9728 KB Output is correct
16 Correct 7 ms 9820 KB Output is correct
17 Correct 6 ms 9820 KB Output is correct
18 Correct 7 ms 9816 KB Output is correct
19 Correct 7 ms 10072 KB Output is correct
20 Correct 10 ms 10076 KB Output is correct
21 Correct 8 ms 10072 KB Output is correct
22 Correct 17 ms 13852 KB Output is correct
23 Correct 17 ms 13852 KB Output is correct
24 Correct 17 ms 13748 KB Output is correct
25 Correct 17 ms 13852 KB Output is correct
26 Correct 16 ms 13848 KB Output is correct
27 Correct 9 ms 10428 KB Output is correct
28 Correct 9 ms 10428 KB Output is correct
29 Correct 10 ms 10428 KB Output is correct
30 Correct 37 ms 17968 KB Output is correct
31 Correct 32 ms 17876 KB Output is correct
32 Correct 34 ms 18016 KB Output is correct
33 Correct 45 ms 16840 KB Output is correct
34 Correct 52 ms 17200 KB Output is correct
35 Correct 46 ms 16708 KB Output is correct
36 Correct 722 ms 90864 KB Output is correct
37 Correct 796 ms 90632 KB Output is correct
38 Correct 716 ms 90552 KB Output is correct
39 Correct 296 ms 33864 KB Output is correct
40 Correct 281 ms 33832 KB Output is correct
41 Correct 245 ms 33708 KB Output is correct
42 Correct 84 ms 23380 KB Output is correct
43 Correct 707 ms 143444 KB Output is correct
44 Correct 834 ms 143620 KB Output is correct
45 Correct 719 ms 143400 KB Output is correct
46 Correct 863 ms 143412 KB Output is correct
47 Correct 739 ms 143716 KB Output is correct
48 Correct 763 ms 143516 KB Output is correct
49 Correct 740 ms 143668 KB Output is correct
50 Correct 747 ms 143444 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 7 ms 9852 KB Output is correct
3 Correct 7 ms 9820 KB Output is correct
4 Correct 7 ms 9828 KB Output is correct
5 Correct 5 ms 9828 KB Output is correct
6 Correct 7 ms 9828 KB Output is correct
7 Correct 5 ms 9864 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 7 ms 9828 KB Output is correct
10 Correct 5 ms 9832 KB Output is correct
11 Correct 7 ms 9928 KB Output is correct
12 Correct 7 ms 9832 KB Output is correct
13 Correct 6 ms 9788 KB Output is correct
14 Correct 5 ms 9832 KB Output is correct
15 Correct 6 ms 9728 KB Output is correct
16 Correct 7 ms 9820 KB Output is correct
17 Correct 6 ms 9820 KB Output is correct
18 Correct 7 ms 9816 KB Output is correct
19 Correct 7 ms 10072 KB Output is correct
20 Correct 10 ms 10076 KB Output is correct
21 Correct 8 ms 10072 KB Output is correct
22 Correct 17 ms 13852 KB Output is correct
23 Correct 17 ms 13852 KB Output is correct
24 Correct 17 ms 13748 KB Output is correct
25 Correct 17 ms 13852 KB Output is correct
26 Correct 16 ms 13848 KB Output is correct
27 Correct 136 ms 29316 KB Output is correct
28 Correct 155 ms 25228 KB Output is correct
29 Correct 128 ms 25284 KB Output is correct
30 Correct 120 ms 28924 KB Output is correct
31 Correct 132 ms 23968 KB Output is correct
32 Correct 688 ms 77228 KB Output is correct
33 Correct 148 ms 27520 KB Output is correct
34 Correct 229 ms 35988 KB Output is correct
35 Correct 5 ms 9816 KB Output is correct
36 Correct 754 ms 89788 KB Output is correct
37 Correct 2647 ms 260000 KB Output is correct
38 Correct 2627 ms 260680 KB Output is correct
39 Correct 2041 ms 160052 KB Output is correct
40 Correct 769 ms 89668 KB Output is correct
41 Correct 299 ms 46104 KB Output is correct
42 Correct 35 ms 19736 KB Output is correct
43 Correct 2805 ms 178716 KB Output is correct
44 Correct 1552 ms 146856 KB Output is correct
45 Execution timed out 3004 ms 476656 KB Time limit exceeded
46 Halted 0 ms 0 KB -