oj.uz

Submission #103657

# Submission time Handle Problem Language Result Execution time Memory
103657 2019-04-01T20:10:34 Z osaaateiasavtnl Circle selection (APIO18_circle_selection) C++14
72 / 100
 3000 ms 40764 KB 
#include<bits/stdc++.h>
using namespace std;
#define Point pair <int, int>
#define x first
#define y second
const int N = 3e5 + 7;
int n;
Point a[N];
int r[N];
int par[N];
int cur = 1 << 30;
vector<vector<int>> av;
vector<int> px;
int per[N];
bool compx(int i, int j) {
    return a[i].x < a[j].x;
}   
bool compy(int i, int j) {
    return a[i].y < a[j].y;
}   
bool used[N];
struct Comp {
    bool operator () (const int i, const int j) {
        return (r[i] > r[j]) || (r[i] == r[j] && i < j);
    }   
};
set <int,Comp> ms;
void build() {
    av.clear(); px.clear();
    int ptr = 0;
    while (ptr < n) {
        int r = ptr;
        while (r + 1 < n && a[per[ptr]].x / cur == a[per[r + 1]].x / cur) ++r;
        av.push_back({});
        for (int i = ptr; i <= r; ++i) {
            av.back().push_back(per[i]);
        }
        sort(av.back().begin(), av.back().end(), compy);
        px.push_back(a[per[ptr]].x / cur);
        ptr = r + 1;
    }   
}   
bool intersect(int i, int j) {
    typedef long long ll;
    return (ll)(a[i].x - a[j].x) * (a[i].x - a[j].x) + (ll)(a[i].y - a[j].y) * (a[i].y - a[j].y) <= (ll)(r[i] + r[j]) * (r[i] + r[j]);
}   
void check(int el, int i) {
    #ifdef HOME
    cout << "check " << el + 1 << ' ' << i + 1 << '\n';
    #endif
    if (used[i]) return;
    if (intersect(el, i)) {
        used[i] = 1;
        par[i] = el;
        ms.erase(i);
    }   
}   
void work(int el, int x, int y) {
    auto t = lower_bound(px.begin(), px.end(), x);
    if (*t == x) {
        int pos = t - px.begin();
        #ifdef HOME
        cout << "work " << el + 1 << ' ' << pos << '\n';
        #endif
        int l = -1, r = av[pos].size();
        while (l < r - 1) {
            int m = (l + r) >> 1;
            int i = av[pos][m];
            if (a[i].y / cur < y) l = m;
            else r = m;
        }   
        for (int i = r; i < (int)av[pos].size(); ++i) {
            if (a[av[pos][i]].y / cur != y) {
                break;
            }   
            check(el, av[pos][i]);
        }
    }   
}
void print_struct() {
    for (int i = 0; i < (int)av.size(); ++i) {
        cout << px[i] << " : ";
        for (int t : av[i]) cout << t + 1 << ' ';
        cout << '\n';
    }   
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].x >> a[i].y >> r[i];
    }   
    for (int i = 0; i < n; ++i) {
        per[i] = i;
    }   
    sort(per, per + n, compx);
    for (int i = 0; i < n; ++i) {
        ms.insert(i);
    }   
    build();
    while (ms.size()) {
        int i = *ms.begin();
        bool upd = 0;
        while ((cur >> 1) >= r[i]) {
            cur >>= 1;
            upd = 1;
        }
        if (upd) {
            build();
        }   
        #ifdef HOME
        cout << "eliminate " << i + 1 << '\n';
        cout << "cur " << cur << '\n';
        print_struct();
        #endif
        int ix = a[i].x / cur, iy = a[i].y / cur;
        for (int dx = -2; dx <= 2; ++dx) {
            for (int dy = -2; dy <= 2; ++dy) {
                work(i, ix + dx, iy + dy);
            }   
        }   
    }   
    for (int i = 0; i < n; ++i) {
        cout << par[i] + 1 << ' ';
    }   
    cout << '\n';
}

Subtask #1
7.0 / 7.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 981 ms 24692 KB Output is correct
2 Correct 1049 ms 24384 KB Output is correct
3 Correct 1096 ms 24472 KB Output is correct
4 Correct 943 ms 24024 KB Output is correct
5 Correct 1002 ms 30644 KB Output is correct
6 Correct 1666 ms 38480 KB Output is correct
7 Correct 1406 ms 36416 KB Output is correct
8 Correct 1170 ms 38708 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 692 ms 11572 KB Output is correct
3 Execution timed out 3016 ms 38524 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1526 ms 26488 KB Output is correct
2 Correct 1052 ms 40756 KB Output is correct
3 Correct 954 ms 23692 KB Output is correct
4 Correct 1219 ms 40748 KB Output is correct
5 Correct 1196 ms 40764 KB Output is correct
6 Correct 915 ms 23532 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 10 ms 768 KB Output is correct
21 Correct 11 ms 768 KB Output is correct
22 Correct 27 ms 1144 KB Output is correct
23 Correct 21 ms 1024 KB Output is correct
24 Correct 20 ms 1200 KB Output is correct
25 Correct 21 ms 1152 KB Output is correct
26 Correct 22 ms 1024 KB Output is correct
27 Correct 18 ms 1152 KB Output is correct
28 Correct 15 ms 1152 KB Output is correct
29 Correct 15 ms 1152 KB Output is correct
30 Correct 59 ms 1628 KB Output is correct
31 Correct 40 ms 1784 KB Output is correct
32 Correct 37 ms 1808 KB Output is correct
33 Correct 231 ms 8304 KB Output is correct
34 Correct 197 ms 8356 KB Output is correct
35 Correct 401 ms 7772 KB Output is correct
36 Correct 749 ms 12172 KB Output is correct
37 Correct 722 ms 12076 KB Output is correct
38 Correct 754 ms 12168 KB Output is correct
39 Correct 738 ms 8388 KB Output is correct
40 Correct 661 ms 8336 KB Output is correct
41 Correct 649 ms 8544 KB Output is correct
42 Correct 268 ms 8412 KB Output is correct
43 Correct 313 ms 13520 KB Output is correct
44 Correct 327 ms 13524 KB Output is correct
45 Correct 359 ms 13356 KB Output is correct
46 Correct 325 ms 13416 KB Output is correct
47 Correct 365 ms 13428 KB Output is correct
48 Correct 365 ms 13392 KB Output is correct
49 Correct 307 ms 13536 KB Output is correct
50 Correct 308 ms 13520 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 3 ms 512 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 10 ms 768 KB Output is correct
21 Correct 11 ms 768 KB Output is correct
22 Correct 27 ms 1144 KB Output is correct
23 Correct 21 ms 1024 KB Output is correct
24 Correct 20 ms 1200 KB Output is correct
25 Correct 21 ms 1152 KB Output is correct
26 Correct 22 ms 1024 KB Output is correct
27 Correct 981 ms 24692 KB Output is correct
28 Correct 1049 ms 24384 KB Output is correct
29 Correct 1096 ms 24472 KB Output is correct
30 Correct 943 ms 24024 KB Output is correct
31 Correct 1002 ms 30644 KB Output is correct
32 Correct 1666 ms 38480 KB Output is correct
33 Correct 1406 ms 36416 KB Output is correct
34 Correct 1170 ms 38708 KB Output is correct
35 Correct 2 ms 384 KB Output is correct
36 Correct 692 ms 11572 KB Output is correct
37 Execution timed out 3016 ms 38524 KB Time limit exceeded
38 Halted 0 ms 0 KB -