Submission #734476

#	Time	Username	Problem	Language	Result	Execution time	Memory
734476		vjudge1	Circle selection (APIO18_circle_selection)	C++14	100 / 100	622 ms	41028 KiB

circle_selection

#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
  int x = 0, f = 1, ch = getchar();
  while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
  while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
  return x * f;
}
using ll = long long;
const int maxn = 300005;
const int inf = 1e9;
struct hash_table {
  #define mod 611953
  #define base 7919
  std::list <int> v[mod];
  inline int ask (int x, int y) {
    return ((1ll * base * x + y) % mod + mod) % mod;
  }
  inline void ins (int x, int y, int id) {
    v[ask (x, y)].push_back (id);
  }
  inline void clear (void) {
    FOR(i,0,mod-1) v[i].clear();
  }
  #undef mod
  #undef base
} ht;
struct Node {
  int x, y, r;
} node[maxn];
inline ll pw (ll x) { return x * x; }
inline bool check (int p, int q) {
  return pw (node[p].x - node[q].x) + pw (node[p].y - node[q].y) <= pw (node[p].r + node[q].r);
}
int n, B, a[maxn], ans[maxn];
inline bool cmp (int p, int q) {
  return node[p].r != node[q].r ? node[p].r > node[q].r : p < q;
}
inline void rebuild (int r) {
  ht.clear (); B = r; FOR(i,1,n) if(!ans[i])
    ht.ins ((node[i].x + inf) / B, (node[i].y + inf) / B, i);
}
int main (void) {
  n = read();
  FOR(i,1,n) {
    int x = read(), y = read(), r = read();
    node[i] = {x, y, r};
  }
  std::iota (a+1, a+n+1, 1);
  std::sort (a+1, a+n+1, cmp);
  rebuild (node[a[1]].r * 2);
  FOR(i,1,n) if(!ans[a[i]]) {
    if(B > 4ll * node[a[i]].r) rebuild (node[a[i]].r * 2);
    int x = (node[a[i]].x + inf) / B, y = (node[a[i]].y + inf) / B, k;
    FOR(dx,-1,1) FOR(dy,-1,1) {
      k = ht.ask (x + dx, y + dy);
      for(auto it=ht.v[k].begin(); it!=ht.v[k].end(); )
        if(check(a[i], *it)) {
          ans[*it] = a[i];
          ht.v[k].erase (it ++);
        } else ++ it;
    }
  }
  FOR(i,1,n) printf("%d%c", ans[i], i==n?10:32);
  return 0;
}

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