oj.uz

Submission #87150

# Submission time Handle Problem Language Result Execution time Memory
87150 2018-11-29T18:05:29 Z fedoseevtimofey Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 59608 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

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
    int n;
    cin >> n;
    vector <int> x(n), y(n), r(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i] >> r[i];
    vector <int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    vector <int> who(n, -1);
    sort(idx.begin(), idx.end(), [&] (int i, int j) {
        if (r[i] != r[j]) return r[i] > r[j];
        return i < j;
    });
    for (int i : idx) {
        if (who[i] != -1) continue;
        who[i] = i + 1;
        for (int j = 0; j < n; ++j) {
            if (who[j] == -1 && (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])) {
                who[j] = i + 1;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << who[i] << ' ';
    }
}

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 384 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 3 ms 748 KB Output is correct
17 Correct 3 ms 952 KB Output is correct
18 Correct 3 ms 952 KB Output is correct
19 Correct 6 ms 1104 KB Output is correct
20 Correct 5 ms 1272 KB Output is correct
21 Correct 5 ms 1424 KB Output is correct
22 Correct 109 ms 1596 KB Output is correct
23 Correct 111 ms 1744 KB Output is correct
24 Correct 119 ms 1868 KB Output is correct
25 Correct 87 ms 1992 KB Output is correct
26 Correct 90 ms 2120 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 16612 KB Output is correct
2 Correct 201 ms 23396 KB Output is correct
3 Correct 234 ms 29736 KB Output is correct
4 Correct 194 ms 36824 KB Output is correct
5 Execution timed out 3015 ms 39436 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 39436 KB Output is correct
2 Execution timed out 3031 ms 39436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 3 ms 748 KB Output is correct
17 Correct 3 ms 952 KB Output is correct
18 Correct 3 ms 952 KB Output is correct
19 Correct 6 ms 1104 KB Output is correct
20 Correct 5 ms 1272 KB Output is correct
21 Correct 5 ms 1424 KB Output is correct
22 Correct 109 ms 1596 KB Output is correct
23 Correct 111 ms 1744 KB Output is correct
24 Correct 119 ms 1868 KB Output is correct
25 Correct 87 ms 1992 KB Output is correct
26 Correct 90 ms 2120 KB Output is correct
27 Correct 8 ms 50036 KB Output is correct
28 Correct 8 ms 50036 KB Output is correct
29 Correct 8 ms 50036 KB Output is correct
30 Correct 393 ms 50036 KB Output is correct
31 Correct 391 ms 50036 KB Output is correct
32 Correct 391 ms 50036 KB Output is correct
33 Correct 67 ms 51716 KB Output is correct
34 Correct 72 ms 54712 KB Output is correct
35 Correct 72 ms 57672 KB Output is correct
36 Execution timed out 3033 ms 59608 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 616 KB Output is correct
8 Correct 2 ms 748 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 3 ms 748 KB Output is correct
17 Correct 3 ms 952 KB Output is correct
18 Correct 3 ms 952 KB Output is correct
19 Correct 6 ms 1104 KB Output is correct
20 Correct 5 ms 1272 KB Output is correct
21 Correct 5 ms 1424 KB Output is correct
22 Correct 109 ms 1596 KB Output is correct
23 Correct 111 ms 1744 KB Output is correct
24 Correct 119 ms 1868 KB Output is correct
25 Correct 87 ms 1992 KB Output is correct
26 Correct 90 ms 2120 KB Output is correct
27 Correct 178 ms 16612 KB Output is correct
28 Correct 201 ms 23396 KB Output is correct
29 Correct 234 ms 29736 KB Output is correct
30 Correct 194 ms 36824 KB Output is correct
31 Execution timed out 3015 ms 39436 KB Time limit exceeded
32 Halted 0 ms 0 KB -