oj.uz

Submission #1070463

# Submission time Handle Problem Language Result Execution time Memory
1070463 2024-08-22T14:29:44 Z thangdz2k7 Circle selection (APIO18_circle_selection) C++17
19 / 100
 645 ms 47864 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

long long sqr(long long x){ return x * x; }

struct circle{
    long long x, y, r;

    bool intersect(circle A){
        return sqr(x - A.x) + sqr(y - A.y) <= sqr(r + A.r);
    }
};

int n;
circle a[N];

namespace subtask1{
    int ans[N];

    void solve(){
        while (true){
            long long maxr = 0;
            int idx = 0;
            for (int i = 1; i <= n; ++ i) if (!ans[i] && a[i].r > maxr){
                idx = i;
                maxr = a[i].r;
            }
            if (!idx) break;
            for (int i = 1; i <= n; ++ i) if (!ans[i] && a[idx].intersect(a[i])) ans[i] = idx;
        }
        for (int i = 1; i <= n; ++ i) cout << ans[i] << ' ';
    }
}

namespace subtask2{
    vector <int> sr;
    int ans[N];
    set <pair <int, int>> l, r;

    void solve(){
        for (int i = 1; i <= n; ++ i) {
            sr.push_back(i);
            l.insert({a[i].x - a[i].r, i});
            r.insert({a[i].x + a[i].r, i});
        }
        sort(sr.begin(), sr.end(), [&](int u, int v){
            if (a[u].r == a[v].r) return u < v;
            return a[u].r > a[v].r;
        });

        for (int id : sr){
            if (ans[id]) continue;
            int le = a[id].x - a[id].r;
            int ri = a[id].x + a[id].r;
            auto it = l.lower_bound({le, 0});
            while (it != l.end() && it -> first <= ri){
                int del = it -> second;
                ans[del] = id;
                ++ it;
                l.erase({a[del].x - a[del].r, del});
                r.erase({a[del].x + a[del].r, del});
            }
            it = r.lower_bound({le, 0});
            while (it != r.end() && it -> first <= ri){
                int del = it -> second;
                ans[del] = id;
                ++ it;
                l.erase({a[del].x - a[del].r, del});
                r.erase({a[del].x + a[del].r, del});
            }
        }

        for (int i = 1; i <= n; ++ i) cout << ans[i] << ' ';
    }
}

namespace subtask4{
    void solve(){

    }
}

namespace Acepted{
    void solve(){

    }
}

void solve(){
    cin >> n;
    bool ck2 = true;
    bool ck4 = true;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i].x >> a[i].y >> a[i].r;
        if (a[i].y != 0) ck2 = false;
        if (i > 1 && a[i].r != a[i - 1].r) ck4 = false;
    }

    if (n <= 5000) subtask1::solve();
    else if (ck2) subtask2::solve();
    else if (ck4) subtask4::solve();
    else Acepted::solve();
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 4528 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2576 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Correct 2 ms 4700 KB Output is correct
21 Correct 3 ms 2652 KB Output is correct
22 Correct 59 ms 2748 KB Output is correct
23 Correct 60 ms 2756 KB Output is correct
24 Correct 59 ms 2756 KB Output is correct
25 Correct 59 ms 2760 KB Output is correct
26 Correct 59 ms 2652 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 47864 KB Output is correct
2 Correct 612 ms 47756 KB Output is correct
3 Correct 593 ms 47696 KB Output is correct
4 Correct 645 ms 47832 KB Output is correct
5 Correct 479 ms 45720 KB Output is correct
6 Correct 494 ms 45760 KB Output is correct
7 Correct 480 ms 45756 KB Output is correct
8 Correct 489 ms 45752 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 23 ms 7540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 17408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 4528 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2576 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Correct 2 ms 4700 KB Output is correct
21 Correct 3 ms 2652 KB Output is correct
22 Correct 59 ms 2748 KB Output is correct
23 Correct 60 ms 2756 KB Output is correct
24 Correct 59 ms 2756 KB Output is correct
25 Correct 59 ms 2760 KB Output is correct
26 Correct 59 ms 2652 KB Output is correct
27 Incorrect 5 ms 3164 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2520 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 4528 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2576 KB Output is correct
19 Correct 3 ms 2652 KB Output is correct
20 Correct 2 ms 4700 KB Output is correct
21 Correct 3 ms 2652 KB Output is correct
22 Correct 59 ms 2748 KB Output is correct
23 Correct 60 ms 2756 KB Output is correct
24 Correct 59 ms 2756 KB Output is correct
25 Correct 59 ms 2760 KB Output is correct
26 Correct 59 ms 2652 KB Output is correct
27 Correct 571 ms 47864 KB Output is correct
28 Correct 612 ms 47756 KB Output is correct
29 Correct 593 ms 47696 KB Output is correct
30 Correct 645 ms 47832 KB Output is correct
31 Correct 479 ms 45720 KB Output is correct
32 Correct 494 ms 45760 KB Output is correct
33 Correct 480 ms 45756 KB Output is correct
34 Correct 489 ms 45752 KB Output is correct
35 Correct 1 ms 4444 KB Output is correct
36 Incorrect 23 ms 7540 KB Output isn't correct
37 Halted 0 ms 0 KB -