oj.uz

답안 #440135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440135 2021-07-01T16:05:42 Z KULIKOLD 원 고르기 (APIO18_circle_selection) C++17
7 / 100
 1723 ms 1048580 KB 
//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int DIM = 1E5+7;
const int INF = 1E9;
struct node{
    ll x,y,r,pos;
} A[DIM];
int P[DIM],ans[DIM];
bool mc(const node &a,const node &b){
    if (a.r==b.r){
        return a.pos<b.pos;
    }
    return a.r>b.r;
}
bool can(const node &a,const node &b){
    return (a.r+b.r)*(a.r+b.r)>=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int n;
int solve(){


    sort(A+1,A+1+n,mc);
    for(int i = 1;i<=n;++i){
        if (P[i])
            continue;
        P[i] = i;
        ans[A[i].pos] = A[i].pos;
        for(int j = i+1;j<=n;++j)
            if (!P[j] && can(A[i],A[j]))
                P[j] = i,ans[A[j].pos] = A[i].pos;
    }
    for(int i = 1;i<=n;++i)
        cout<<ans[i]<<' ';
    cout<<endl;
    return 1;
}
void solve1(){
    set<pair<ll,ll> > SL,SR;
    sort(A+1,A+1+n,mc);
    for(int i = 1;i<=n;++i){
        SL.insert({A[i].x-A[i].r,i});
        SR.insert({A[i].x+A[i].r,i});
    }

    for(int i = 1;i<=n;++i){
        vector<int> V;
        {
            auto it = SL.lower_bound({A[i].x - A[i].r, 0});

            while (it != SL.end() && it->first <= A[i].x + A[i].r) {
                ans[A[it->second].pos] = A[i].pos;
                V.push_back(it->second);
                it = next(it);
            }
        }
        {
            auto it = SR.upper_bound({A[i].x+A[i].r,INF});
            if (it!=SR.begin()){
                it = prev(it);
                while(1 && it->first>=A[i].x-A[i].r){
                    ans[A[it->second].pos] = A[i].pos;
                    V.push_back(it->second);
                    if (it==SR.begin())
                        break;
                }
            }
        }
        for(int i:V){
            SL.erase({A[i].x-A[i].r,i});
            SR.erase({A[i].x+A[i].r,i});
        }
    }
    for(int i = 1;i<=n;++i)
        cout<<ans[i]<<' ';
    cout<<endl;
}
int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;++i){
        cin>>A[i].x>>A[i].y>>A[i].r;
        A[i].pos = i;
    }
    if (n<=5000)
        solve();
    else
        solve1();
    return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 460 KB Output is correct
20 Correct 4 ms 460 KB Output is correct
21 Correct 3 ms 460 KB Output is correct
22 Correct 29 ms 460 KB Output is correct
23 Correct 31 ms 512 KB Output is correct
24 Correct 32 ms 508 KB Output is correct
25 Correct 33 ms 520 KB Output is correct
26 Correct 29 ms 512 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 46 ms 6736 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 1723 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 8004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 460 KB Output is correct
20 Correct 4 ms 460 KB Output is correct
21 Correct 3 ms 460 KB Output is correct
22 Correct 29 ms 460 KB Output is correct
23 Correct 31 ms 512 KB Output is correct
24 Correct 32 ms 508 KB Output is correct
25 Correct 33 ms 520 KB Output is correct
26 Correct 29 ms 512 KB Output is correct
27 Runtime error 1595 ms 1048580 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 4 ms 460 KB Output is correct
20 Correct 4 ms 460 KB Output is correct
21 Correct 3 ms 460 KB Output is correct
22 Correct 29 ms 460 KB Output is correct
23 Correct 31 ms 512 KB Output is correct
24 Correct 32 ms 508 KB Output is correct
25 Correct 33 ms 520 KB Output is correct
26 Correct 29 ms 512 KB Output is correct
27 Runtime error 46 ms 6736 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -