oj.uz

Submission #252071

# Submission time Handle Problem Language Result Execution time Memory
252071 2020-07-24T05:54:38 Z Mlxa Circle selection (APIO18_circle_selection) C++14
7 / 100
 3000 ms 21216 KB 
#include <bits/stdc++.h>
using ll = long long;
#define int ll
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
using namespace std;

const int N = 3e5 + 5;
int n;
int x[N];
int y[N];
int r[N];
int a[N];
int step = 30;
vector<int> desc;

int sq(int t) {
    return t * t;
}
bool cross(int i, int j) {
    return sq(x[i] - x[j]) + sq(y[i] - y[j]) <= sq(r[i] + r[j]);
}

int id(int xi, int yi) {
    return ((xi >> step) << 30) ^ (yi >> step);
}
map<int, vector<int>> table;

void build() {
    table.clear();
    for (int i = 0; i < n; ++i) {
        if (a[i] == -1) {
            table[id(x[i], y[i])].push_back(i);
        }
    }
}

signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif // LC
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> r[i];
        a[i] = -1;
        desc.push_back(i);
    }
    sort(all(desc), [&](int i, int j) {
         return mp(-r[i], i) < mp(-r[j], j);
    });
    for (int i : desc) {
        if (a[i] != -1) {
            continue;
        }
        /*assert((1LL << step) >= 2 * r[i]);
        while ((1LL << step) >= 4 * r[i]) {
            --step;
            build();
        }
        int delta = 1LL << step;
        for (int dx = -delta; dx <= +delta; dx += delta) {
            for (int dy = -delta; dy <= +delta; dy += delta) {
                int v = id(x[i] + dx, y[i] + dy);
                if (!table.count(v)) {
                    continue;
                }
                vector<int> tmp;
                for (int j : table[v]) {
                    if (cross(i, j)) {
                        assert(a[j] == -1);
                        a[j] = i;
                    } else {
                        tmp.push_back(j);
                    }
                }
                table[v] = tmp;
            }
        }*/
        for (int j = 0; j < n; ++j) {
            if (a[j] == -1 && cross(i, j)) {
                a[j] = i;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        cout << a[i] + 1 << " ";
    }
    cout << "\n";
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 4 ms 768 KB Output is correct
20 Correct 4 ms 820 KB Output is correct
21 Correct 4 ms 768 KB Output is correct
22 Correct 60 ms 768 KB Output is correct
23 Correct 60 ms 768 KB Output is correct
24 Correct 59 ms 768 KB Output is correct
25 Correct 59 ms 768 KB Output is correct
26 Correct 59 ms 768 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 14304 KB Output is correct
2 Correct 189 ms 20960 KB Output is correct
3 Correct 191 ms 20704 KB Output is correct
4 Correct 178 ms 21216 KB Output is correct
5 Execution timed out 3069 ms 16996 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Execution timed out 3054 ms 4464 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 3080 ms 13116 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 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 4 ms 768 KB Output is correct
20 Correct 4 ms 820 KB Output is correct
21 Correct 4 ms 768 KB Output is correct
22 Correct 60 ms 768 KB Output is correct
23 Correct 60 ms 768 KB Output is correct
24 Correct 59 ms 768 KB Output is correct
25 Correct 59 ms 768 KB Output is correct
26 Correct 59 ms 768 KB Output is correct
27 Correct 11 ms 1280 KB Output is correct
28 Correct 7 ms 1280 KB Output is correct
29 Correct 7 ms 1280 KB Output is correct
30 Correct 274 ms 1272 KB Output is correct
31 Correct 271 ms 1272 KB Output is correct
32 Correct 308 ms 1272 KB Output is correct
33 Correct 71 ms 8176 KB Output is correct
34 Correct 67 ms 8192 KB Output is correct
35 Correct 70 ms 7920 KB Output is correct
36 Execution timed out 3057 ms 6892 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 4 ms 768 KB Output is correct
20 Correct 4 ms 820 KB Output is correct
21 Correct 4 ms 768 KB Output is correct
22 Correct 60 ms 768 KB Output is correct
23 Correct 60 ms 768 KB Output is correct
24 Correct 59 ms 768 KB Output is correct
25 Correct 59 ms 768 KB Output is correct
26 Correct 59 ms 768 KB Output is correct
27 Correct 177 ms 14304 KB Output is correct
28 Correct 189 ms 20960 KB Output is correct
29 Correct 191 ms 20704 KB Output is correct
30 Correct 178 ms 21216 KB Output is correct
31 Execution timed out 3069 ms 16996 KB Time limit exceeded
32 Halted 0 ms 0 KB -