Submission #698932

#	Time	Username	Problem	Language	Result	Execution time	Memory
698932		vjudge1	Circle selection (APIO18_circle_selection)	C++17	0 / 100	3008 ms	65260 KiB

circle_selection

#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;};
struct event {int t, x, y, i;};
bool operator<(circle a, circle b) {if (a.r == b.r) return a.i < b.i; return a.r > b.r;};
bool operator<(event a, event b) {return (a.t == b.t? (a.i%3 == b.i%3?a.i/3 > b.i/3: a.i%3 < b.i%3) : a.t < b.t);}
int p[M];
    
int sq(int a) {return a*a;}
int dist(int x1, int y1, int x2, int y2) {
    return sq(x1-x2) + sq(y1-y2);
}

int cnt;
vector<circle> dnc(vector<circle> v) {
    if (v.size() <= 1) return v;

    vector<circle> a, b;
    int n = v.size(), m = n/2;
    for (int i = 0; i < m; i++) a.push_back(v[i]);
    for (int i = m; i < n; i++) b.push_back(v[i]);

    int tmp = ++cnt;
    a = dnc(a);

    multiset<event> timeline;
    for (auto [x, y, r, i]:b) timeline.insert({x-r, x, y, 3*i + 1}), timeline.insert({x+r, x, y, 3*i + 1});
    for (auto [x, y, r, i]:a) timeline.insert({x-r, x, y, 3*i}),     timeline.insert({x+r, x, y, 3*i + 2});

    vector<circle> end;
    multiset<circle> st;
    for (auto [t, x, y, i]:timeline) {
        if (i%3 == 0) st.insert({x, y, x-t, i/3});
        if (i%3 == 1) {
            i /= 3;
            int r = abs(t-x);
            for (auto [x2, y2, r2, i2]:st) 
                if (dist(x, y, x2, y2) <= sq(r + r2))
                    p[i] = max(p[i], i2);

            if (!p[i] && t > x) end.push_back({x, y, r, i});
        }

        // if (i%3 == 2) st.erase(st.find({x, y, t-x, i/3}));
    }

    end = dnc(end);
    for (auto i:a) end.push_back(i);
    return end;
}

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

    int n;
    cin >> n;

    vector<circle> v;
    for (int i = 1; i <= n; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        v.push_back({x, y, r, i});
    } sort(v.begin(), v.end());
    for (auto [a, b, c, i]:v) cout << i << ' '; cout << endl;

    for (auto [a, b, c, i]:dnc(v)) p[i] = i;
    // dnc(v);

    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
-------

7
1
3
4 8 10

2 5 6 9 11 

*/

Compilation message (stderr)

circle_selection.cpp: In function 'std::vector<circle> dnc(std::vector<circle>)':
circle_selection.cpp:28:9: warning: unused variable 'tmp' [-Wunused-variable]
   28 |     int tmp = ++cnt;
      |         ^~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:69:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   69 |     for (auto [a, b, c, i]:v) cout << i << ' '; cout << endl;
      |     ^~~
circle_selection.cpp:69:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   69 |     for (auto [a, b, c, i]:v) cout << i << ' '; cout << endl;
      |                                                 ^~~~
circle_selection.cpp:74:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   74 |     for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
      |     ^~~
circle_selection.cpp:74:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   74 |     for (int i = 1; i <= n; i++) cout << p[i] << ' '; cout << endl;
      |                                                       ^~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13