oj.uz

Submission #87160

# Submission time Handle Problem Language Result Execution time Memory
87160 2018-11-29T19:12:43 Z fedoseevtimofey Circle selection (APIO18_circle_selection) C++14
49 / 100
 3000 ms 286184 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int n;
vector <int> x, y, r;
 
void init() {
    cin >> n;
    x.resize(n);
    y.resize(n);
    r.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> r[i];
    }
}
 
bool inter(int i, int j) {
    return (ll)(x[i] - x[j]) * (x[i] - x[j]) + (ll)(y[i] - y[j]) * (y[i] - y[j]) <= (ll)(r[i] + r[j]) * (r[i] + r[j]);
}
 
unordered_map <int, unordered_map <int, vector <int>>> who;
 
set <int> alive;
 
void rebuild(int B) {
    who.clear();
    for (auto i : alive) {
        int xx = x[i] / B;
        int yy = y[i] / B;
        who[xx][yy].push_back(i);
    }
}
 
void solve() {
    for (int i = 0; i < n; ++i) alive.insert(i);
    vector <int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&] (int i, int j) {
        if (r[i] != r[j]) return r[i] > r[j];
        return i < j;
    });
    vector <int> kill(n, -1);
    int uk = 0;
    for (int B = 1 << 30; B > 0; B >>= 1) {
        bool fl = false;
        while (true) {
            while (uk < n && kill[idx[uk]] != -1) ++uk;
            if (uk == n) break;
            int cur = idx[uk];
            if (!fl) {
                B = r[cur];
                rebuild(B);
                fl = true; 
            }
            else {
                if (B >> 1 >= r[cur]) break;
            }
            alive.erase(cur);
            kill[cur] = cur;
            int xx = x[cur] / B;
            int yy = y[cur] / B;
            for (int cx = xx - 2; cx <= xx + 2; ++cx) {
                for (int cy = yy - 2; cy <= yy + 2; ++cy) {
                    vector <int> nw;
                    for (auto j : who[cx][cy]) {
                        if (inter(cur, j)) {
                            kill[j] = cur;
                            alive.erase(j);
                        }
                        else {
                            nw.push_back(j);
                        }
                    }
                    who[cx][cy] = nw;
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << kill[i] + 1 << ' ';
    }
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    init();
    solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 580 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 3 ms 876 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 3 ms 876 KB Output is correct
16 Correct 3 ms 876 KB Output is correct
17 Correct 3 ms 876 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 6 ms 1020 KB Output is correct
20 Correct 6 ms 1020 KB Output is correct
21 Correct 7 ms 1036 KB Output is correct
22 Correct 47 ms 5312 KB Output is correct
23 Correct 47 ms 5312 KB Output is correct
24 Correct 42 ms 5532 KB Output is correct
25 Correct 44 ms 6428 KB Output is correct
26 Correct 49 ms 6428 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 22828 KB Output is correct
2 Correct 374 ms 24112 KB Output is correct
3 Correct 350 ms 24112 KB Output is correct
4 Correct 324 ms 24112 KB Output is correct
5 Correct 612 ms 24112 KB Output is correct
6 Correct 1978 ms 86712 KB Output is correct
7 Correct 745 ms 86712 KB Output is correct
8 Correct 915 ms 86712 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 86712 KB Output is correct
2 Correct 2079 ms 86712 KB Output is correct
3 Execution timed out 3052 ms 243176 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 580 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 3 ms 876 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 3 ms 876 KB Output is correct
16 Correct 3 ms 876 KB Output is correct
17 Correct 3 ms 876 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 6 ms 1020 KB Output is correct
20 Correct 6 ms 1020 KB Output is correct
21 Correct 7 ms 1036 KB Output is correct
22 Correct 47 ms 5312 KB Output is correct
23 Correct 47 ms 5312 KB Output is correct
24 Correct 42 ms 5532 KB Output is correct
25 Correct 44 ms 6428 KB Output is correct
26 Correct 49 ms 6428 KB Output is correct
27 Correct 14 ms 286184 KB Output is correct
28 Correct 11 ms 286184 KB Output is correct
29 Correct 11 ms 286184 KB Output is correct
30 Correct 125 ms 286184 KB Output is correct
31 Correct 103 ms 286184 KB Output is correct
32 Correct 139 ms 286184 KB Output is correct
33 Correct 110 ms 286184 KB Output is correct
34 Correct 113 ms 286184 KB Output is correct
35 Correct 123 ms 286184 KB Output is correct
36 Correct 1985 ms 286184 KB Output is correct
37 Correct 1993 ms 286184 KB Output is correct
38 Correct 2011 ms 286184 KB Output is correct
39 Correct 784 ms 286184 KB Output is correct
40 Correct 789 ms 286184 KB Output is correct
41 Correct 796 ms 286184 KB Output is correct
42 Correct 339 ms 286184 KB Output is correct
43 Correct 1191 ms 286184 KB Output is correct
44 Correct 1178 ms 286184 KB Output is correct
45 Correct 1161 ms 286184 KB Output is correct
46 Correct 1191 ms 286184 KB Output is correct
47 Correct 1176 ms 286184 KB Output is correct
48 Correct 1246 ms 286184 KB Output is correct
49 Correct 1243 ms 286184 KB Output is correct
50 Correct 1193 ms 286184 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 580 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 3 ms 876 KB Output is correct
13 Correct 3 ms 876 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 3 ms 876 KB Output is correct
16 Correct 3 ms 876 KB Output is correct
17 Correct 3 ms 876 KB Output is correct
18 Correct 3 ms 876 KB Output is correct
19 Correct 6 ms 1020 KB Output is correct
20 Correct 6 ms 1020 KB Output is correct
21 Correct 7 ms 1036 KB Output is correct
22 Correct 47 ms 5312 KB Output is correct
23 Correct 47 ms 5312 KB Output is correct
24 Correct 42 ms 5532 KB Output is correct
25 Correct 44 ms 6428 KB Output is correct
26 Correct 49 ms 6428 KB Output is correct
27 Correct 343 ms 22828 KB Output is correct
28 Correct 374 ms 24112 KB Output is correct
29 Correct 350 ms 24112 KB Output is correct
30 Correct 324 ms 24112 KB Output is correct
31 Correct 612 ms 24112 KB Output is correct
32 Correct 1978 ms 86712 KB Output is correct
33 Correct 745 ms 86712 KB Output is correct
34 Correct 915 ms 86712 KB Output is correct
35 Correct 2 ms 86712 KB Output is correct
36 Correct 2079 ms 86712 KB Output is correct
37 Execution timed out 3052 ms 243176 KB Time limit exceeded
38 Halted 0 ms 0 KB -