oj.uz

Submission #698690

# Submission time Handle Problem Language Result Execution time Memory
698690 2023-02-14T07:51:49 Z vjudge1 Circle selection (APIO18_circle_selection) C++17
7 / 100
 3000 ms 70976 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'

const int M = 3e5+5, MOD = 1e9;
struct circle {int x, y, r, i;};
bool operator<(circle a, circle b) {if (a.r == b.r) return a.i < b.i; return a.r > b.r;};
int p[M], l[M], r[M];
    
int sq(int a) {return a*a;}
int dist(circle a, circle b) {
    return sq(a.x-b.x) + sq(a.y-b.y);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;

    int mx = INT_MIN;
    set<circle> v;
    set<pair<int, int>> rng;
    for (int i = 1; i <= n; i++) {
        int x, y, r_;
        cin >> x >> y >> r_;

        l[i] = x-r_;
        r[i] = x+r_;
        mx = max(mx, y);
        rng.insert({l[i], i});
        rng.insert({r[i], i});
        v.insert({x, y, r_, i});
    }

    if (mx) {
        while (v.size()) {
            auto a = *v.begin();
            v.erase(v.begin());
            // cout << a.i << ": ";
            p[a.i] = a.i;

            set<circle> st;
            for (auto b:v) {
                if (dist(a, b) <= sq(a.r+b.r)) {
                    p[b.i] = a.i;
                    // cout << b.i << ' ';
                    st.insert(b);
                }
            } //cout << endl;

            for (auto c:st) v.erase(c);
        }
    } else {
        vector<int> ind;
        for (int i = 1; i <= n; i++) ind.push_back(i);
        sort(ind.rbegin(), ind.rend(), [](int a, int b) {if (r[a]-l[a] == r[b]-l[b]) return a < b; return r[a]-l[a] > r[b]-l[b];});
        for (int a:ind) {
            if (rng.find({l[a], a}) == rng.end()) continue;
            p[a] = a;
            auto begin = rng.upper_bound({l[a], a}), end = rng.find({r[a], a});
            auto it = begin;
            while (it != end) {
                // rng.erase({l[it->second], it->second});
                // rng.erase({r[it->second], it->second});
                p[it->second] = a;
                it = next(it);
            }

            // rng.erase(begin);
            // rng.erase(end);
        }
    }

    for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;

    return 0;
}
/*
11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
-------
7 
0 0 2
-1 0 1
0 0 1
1 0 1
10 0 5 
11 0 5
50 0 1
-------
*/

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:77:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   77 |     for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
      |     ^~~
circle_selection.cpp:77:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |     for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
      |                                                       ^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 7 ms 1876 KB Output is correct
20 Correct 7 ms 1876 KB Output is correct
21 Correct 7 ms 1748 KB Output is correct
22 Correct 182 ms 1456 KB Output is correct
23 Correct 189 ms 1472 KB Output is correct
24 Correct 182 ms 1592 KB Output is correct
25 Correct 180 ms 1468 KB Output is correct
26 Correct 184 ms 1584 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 3075 ms 22972 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 3081 ms 66256 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 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 7 ms 1876 KB Output is correct
20 Correct 7 ms 1876 KB Output is correct
21 Correct 7 ms 1748 KB Output is correct
22 Correct 182 ms 1456 KB Output is correct
23 Correct 189 ms 1472 KB Output is correct
24 Correct 182 ms 1592 KB Output is correct
25 Correct 180 ms 1468 KB Output is correct
26 Correct 184 ms 1584 KB Output is correct
27 Correct 17 ms 3328 KB Output is correct
28 Correct 13 ms 3412 KB Output is correct
29 Correct 13 ms 3412 KB Output is correct
30 Correct 928 ms 2600 KB Output is correct
31 Correct 935 ms 2596 KB Output is correct
32 Correct 952 ms 2708 KB Output is correct
33 Correct 281 ms 31332 KB Output is correct
34 Correct 260 ms 31432 KB Output is correct
35 Correct 289 ms 30448 KB Output is correct
36 Execution timed out 3083 ms 22800 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 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 7 ms 1876 KB Output is correct
20 Correct 7 ms 1876 KB Output is correct
21 Correct 7 ms 1748 KB Output is correct
22 Correct 182 ms 1456 KB Output is correct
23 Correct 189 ms 1472 KB Output is correct
24 Correct 182 ms 1592 KB Output is correct
25 Correct 180 ms 1468 KB Output is correct
26 Correct 184 ms 1584 KB Output is correct
27 Execution timed out 3065 ms 70976 KB Time limit exceeded
28 Halted 0 ms 0 KB -