oj.uz

답안 #123916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123916 2019-07-02T09:33:47 Z amiratou 원 고르기 (APIO18_circle_selection) C++14
0 / 100
 666 ms 24860 KB 
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
ii point[300005];
int r[300005];
struct node
{
    int idx;
    node *l,*r;
};
typedef node* pnode;
pnode root = NULL;
bool inter(int i,int j){
    return ((point[i].fi-point[j].fi)*(point[i].fi-point[j].fi)+(point[i].se-point[j].se)*(point[i].se-point[j].se))<=((r[i]+r[j])*(r[i]+r[j]));
}
void insert(pnode &t, pnode it){
    if(!t){
        t=it;
        return ;
    }
    //debugs(t->idx,it->idx);
    //debug(inter(t->idx,it->idx));
    if(inter(t->idx,it->idx))
        insert(t->r,it);
    else
        insert(t->l,it);
}
vii vec;
bool mycomparer(std::pair<int, int> lhs, std::pair<int, int> rhs) {
    if (lhs.first > rhs.first) {
        return true;
    }
    else if (lhs.first == rhs.first && lhs.second < rhs.second) {
        return true;
    }
    else {
        return false;
    }
}
int ans[300005];
void lefty(pnode &t,int id){
    if(!t)return ;
    //debug(t->idx+1);
    ans[t->idx]=id;
    lefty(t->r,id);
    lefty(t->l,id);
}
void solve(pnode &t){
    if(!t)
        return ;
    //debug(t->idx+1);
    ans[t->idx]=t->idx;
    lefty(t->r,t->idx);
    //sep()
    solve(t->l);
}
main(){
    //boost;
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i){
        cin>>point[i].fi>>point[i].se>>r[i];
        vec.pb({r[i],i});
    }
    sort(all(vec),mycomparer);
    for (int i = 0; i < n; ++i){
        pnode curr = new node;
        curr->idx=vec[i].se;
        insert(root,curr);
    }
    solve(root);
    for (int i = 0; i < n; ++i)
        cout<<ans[i]+1<<" ";
    return 0;
}
//long long
//array bounds
//special cases
//binary search

Compilation message

circle_selection.cpp:76:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 3 ms 296 KB Output is correct
6 Runtime error 3 ms 480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 608 ms 24804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 666 ms 24860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 3 ms 296 KB Output is correct
6 Runtime error 3 ms 480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 3 ms 296 KB Output is correct
6 Runtime error 3 ms 480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -