제출 #59937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59937		Flugan42	원 고르기 (APIO18_circle_selection)	C++14	7 / 100	755 ms	35560 KiB

circle_selection

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 1000000000000000000
#define sz(x) (ll)(x).size()
#define all(x) x.begin(),x.end()

struct circle {
  ll x,y,r,id;
} ;
vector< circle > inp;
vi vis;
vii endp,endpy;
circle _;
ll n;

bool mysort(circle a, circle b){
  if (a.r == b.r) return a.id < b.id;
  return a.r > b.r;
}

ld dist(ll i, ll j){
  ll dx = inp[i].x-inp[j].x, dy = inp[i].y-inp[j].y;
  return sqrt(ld(dx*dx)+ld(dy*dy));
}

int main(){
  cin >> n; inp.assign(n,_);
  rep(i,0,n){
    cin >> inp[i].x >> inp[i].y >> inp[i].r;
    inp[i].id = i;
  }
  sort(all(inp),mysort);
  rep(i,0,n){
    endp.push_back(make_pair(inp[i].x-inp[i].r,i));
    endp.push_back(make_pair(inp[i].x+inp[i].r,i));
    endpy.push_back(make_pair(inp[i].y-inp[i].r,i));
    endpy.push_back(make_pair(inp[i].y+inp[i].r,i));
  }
  sort(all(endp));

  if (n <= 10000){
    vis.assign(n,-1);
    rep(i,0,n){
      if (vis[i] != -1) continue;
      rep(j,0,n){
        if (vis[j] != -1) continue;
        if (dist(i,j) <= inp[i].r+inp[j].r) vis[j] = inp[i].id;
      }
    }
  } else {
    vis.assign(n,-1);
    rep(i,0,n){
      if (vis[i] != -1) continue;
      ll lo = lower_bound(all(endp),make_pair(inp[i].x-inp[i].r,0LL))-endp.begin();
      while (endp[lo].first <= inp[i].x+inp[i].r){
        if (vis[endp[lo].second] == -1) vis[endp[lo].second] = i;
        lo++;
      }
    }
  }
  vi res; res.assign(n,0);
  rep(i,0,n){
    res[inp[i].id] = vis[i];
  }
  rep(i,0,n) cout << res[i]+1 << " ";
  cout << endl;
}

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