oj.uz

Submission #1070446

# Submission time Handle Problem Language Result Execution time Memory
1070446 2024-08-22T14:19:09 Z thangdz2k7 Circle selection (APIO18_circle_selection) C++17
7 / 100
 95 ms 16212 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{
    void solve(){

    }
}

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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2508 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 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 2 ms 2396 KB Output is correct
19 Correct 2 ms 2648 KB Output is correct
20 Correct 2 ms 2700 KB Output is correct
21 Correct 2 ms 2532 KB Output is correct
22 Correct 61 ms 2660 KB Output is correct
23 Correct 62 ms 2660 KB Output is correct
24 Correct 67 ms 2668 KB Output is correct
25 Correct 61 ms 2660 KB Output is correct
26 Correct 61 ms 2652 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 16212 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2508 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 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 2 ms 2396 KB Output is correct
19 Correct 2 ms 2648 KB Output is correct
20 Correct 2 ms 2700 KB Output is correct
21 Correct 2 ms 2532 KB Output is correct
22 Correct 61 ms 2660 KB Output is correct
23 Correct 62 ms 2660 KB Output is correct
24 Correct 67 ms 2668 KB Output is correct
25 Correct 61 ms 2660 KB Output is correct
26 Correct 61 ms 2652 KB Output is correct
27 Incorrect 3 ms 2648 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 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2508 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 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 2 ms 2396 KB Output is correct
19 Correct 2 ms 2648 KB Output is correct
20 Correct 2 ms 2700 KB Output is correct
21 Correct 2 ms 2532 KB Output is correct
22 Correct 61 ms 2660 KB Output is correct
23 Correct 62 ms 2660 KB Output is correct
24 Correct 67 ms 2668 KB Output is correct
25 Correct 61 ms 2660 KB Output is correct
26 Correct 61 ms 2652 KB Output is correct
27 Incorrect 95 ms 15128 KB Output isn't correct
28 Halted 0 ms 0 KB -