oj.uz

Submission #123912

# Submission time Handle Problem Language Result Execution time Memory
123912 2019-07-02T09:29:15 Z amiratou Circle selection (APIO18_circle_selection) C++14
0 / 100
 170 ms 20520 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 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 sqrt((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]);
}
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);
}
int 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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 19296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 165 ms 20520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -