oj.uz

답안 #698935

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
698935 2023-02-14T23:33:22 Z vjudge1 원 고르기 (APIO18_circle_selection) C++17
0 / 100
 1237 ms 128508 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;};
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], R[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 dist(circle a, circle b) {
    return sq(a.x-b.x) + sq(a.y-b.y);
}

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]);
    
    a = dnc(a);
    vector<event> timeline;
    for (auto [x, y, r, i]:b) timeline.push_back({x-r, x, y, 3*i + 1}), timeline.push_back({x+r, x, y, 3*i + 1});
    for (auto [x, y, r, i]:a) timeline.push_back({x-r, x, y, 3*i + 0}), timeline.push_back({x+r, x, y, 3*i + 2});
    sort(timeline.begin(), timeline.end());

    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});
        else if (i%3 == 1) {
            i /= 3;
            int r = abs(t-x);
            int sz = (p[i]>M?0:R[p[i]]);
            for (auto [x2, y2, r2, i2]:st) {
                if (dist(x, y, x2, y2) <= sq(r + r2)) {
                    if (r2 > sz) sz = r2, p[i] = i2;
                    else if (r2 == sz) p[i] = min(i2, p[i]);
                }
            }

            if (p[i]>M && t > x) end.push_back({x, y, r, i});
        } else st.erase({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);
    srand(time(0));

    int n;
    cin >> n;

    vector<circle> v;
    for (int i = 1; i <= n; i++) {
        p[i] = INT_MAX;
        int x, y, r;
        cin >> x >> y >> r;
        R[i] = r;
        v.push_back({x, y, r, i});
    } sort(v.begin(), v.end());

    for (auto [a, b, c, i]:dnc(v)) p[i] = i;
    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
-------
5
1 11 10
12 17 4
19 27 6
13 13 5
24 10 10
--------
1 1 3 1 5
*/

Compilation message

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

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 73340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 414 ms 36652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1237 ms 128508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -