Submission #48955

#	Time	Username	Problem	Language	Result	Execution time	Memory
48955		azneye	Circle selection (APIO18_circle_selection)	C++17	87 / 100	3033 ms	761472 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;

namespace {

const unsigned int buffer_size = 1 << 16;
char input_buffer[buffer_size + 1];
unsigned int bytes_read = 0;
unsigned int input_index = 0;

inline char next_char() {
  if (input_index == bytes_read) {
    bytes_read = fread(input_buffer, sizeof(char), buffer_size, stdin);
    input_buffer[bytes_read] = '\0'; //sentinel
    input_index = 0;
  }
  return input_buffer[input_index++];
}

inline int next_int() {
  char c = 0;
  int ans = 0;
  while (c < '-')
    c = next_char();
  bool neg = false;
  if (c == '-') {
    neg = true;
    c = next_char();
  }
  for (; c >= '0'; c = next_char())
    ans = (ans << 1) + (ans << 3) + c - '0';
  return neg ? -ans : ans;
}

inline void next_str(char* str) {
  char c = next_char();
  while (c > ' ') {
    *str++ = c;
    c = next_char();
  }
  *str = '\0';
}

char output_buffer[buffer_size];
unsigned int output_index = 0;

inline void write_flush() {
  fwrite(output_buffer, sizeof(char), output_index, stdout);
  output_index = 0;
}

inline void write_char(char c) {
  output_buffer[output_index++] = c;
  if (output_index == buffer_size)
    write_flush();
}

inline void write_int(int num) {
  if (num >= 10)
    write_int(num / 10);
  write_char(num % 10 + '0');
}

/**
 * Currently this design only allows one arena per arena size
 *
 * @tparam SIZE size of arena in bytes, default is 200 MB
 */
template <size_t SIZE = 500 << 20> class Arena {
  static char buf[];
  static size_t buf_ind;

 public:
  template <class T> struct Allocator {
    typedef T value_type;

    Allocator() {}

    template <class U> Allocator(const U&) {}

    T* allocate(size_t n) {
      buf_ind -= n * sizeof(T);
      buf_ind &= 0 - alignof(T);
      return (T*) (buf + buf_ind);
    }

    void deallocate(T*, size_t) {}
  };

  /**
   * Frees the arena, be very sure no allocation is still used when calling this
   */
  static void Clear() {
    buf_ind = SIZE;
  }
};

template <size_t SIZE> char Arena<SIZE>::buf[SIZE];
template <size_t SIZE> size_t Arena<SIZE>::buf_ind = SIZE;


#define VEVE(i, a, b) for (ll i = a, __##i = b; i < __##i; ++i)
#define DYDY(i, a, b) for (ll i = a, __##i = b; i > __##i; --i)
#define RARA(x, seq) for (auto &x : seq)
#define SIZE(x) ((ll)(x.size()))
#define ALL(x) x.begin(), x.end()

typedef int64_t ll;
typedef double dd;

ll Sq(ll x) {
  return x * x;
}

struct Circle {
  int x, y, r, id;

  bool operator<(const Circle& c) const {
    return make_pair(-r, id) < make_pair(-c.r, c.id);
  }

  bool Contains(int p, int q) const {
    return Sq(p - x) + Sq(q - y) <= Sq(r);
  }

  bool Intersects(const Circle& c) const {
    return Sq(x - c.x) + Sq(y - c.y) <= Sq(r + c.r);
  }

  bool Contains(int x1, int y1, int x2, int y2) const {
    return Contains(x1, y1) and Contains(x1, y2) and Contains(x2, y1) and Contains(x2, y2);
  }

  static bool In(int a, int b, int q) {
    // is q in [a,b]
    return a <= q and q <= b;
  }

  // does this circle intersect square
  // check if an edge intersects
  // or if circle is in square
  bool Intersects(int x1, int y1, int x2, int y2) const {
    return
      // horizontal edge intersects
      (y1 <= y + r and y - r <= y2 and (In(x - r, x + r, x1) or In(x - r, x + r, x2)))
      // vertical edge intersects
      or (x1 <= x + r and x - r <= x2 and (In(y - r, y + r, y1) or In(y - r, y + r, y2)))
      // circle is in square
      or (In(x1, x2, x) and In(y1, y2, y));
  }
};

struct Node {
  static Node pool[];
  static int next_node;
  int quad[4];
  int x1, x2, y1, y2;
  vector<int> ids; // sorted by largest radius first

  Node() {}

  Node(int x1, int y1, int x2, int y2) : x1(x1), x2(x2), y1(y1), y2(y2) {
    memset(quad, 0, sizeof(quad));
  }

  static int Alloc(int x1, int y1, int x2, int y2) {
//    return new(allocator.allocate(1)) Node(x1, x2, y1, y2);
    new(pool + next_node) Node(x1, y1, x2, y2);
    return next_node++;
  }

  void Insert(const vector<Circle>& circs) {
    if (x1 + 1 == x2 or SIZE(circs) <= 500) {
//      DEBUG(x1, y1, x2, y2);
//      RARA(c, circs) DEBUG(c.id);
      RARA(c, circs) {
        ids.push_back(c.id);
//        nodes[c.id].push_back(this);
      }
      return;
    }
    const int xm = (x1 + x2) / 2;
    const int ym = (y1 + y2) / 2;
    vector<Circle> ccs[4];
    RARA(c, circs) {
      if (c.Contains(x1, y1, x2, y2)) {
//        DEBUG(x1, y1, x2, y2, c.id);
        ids.push_back(c.id);
//        nodes[c.id].push_back(this);
        continue;
      }
      if (c.Intersects(xm, ym, x2, y2))
        ccs[0].push_back(c);
      if (c.Intersects(x1, ym, xm, y2))
        ccs[1].push_back(c);
      if (c.Intersects(x1, y1, xm, ym))
        ccs[2].push_back(c);
      if (c.Intersects(xm, y1, x2, ym))
        ccs[3].push_back(c);
    }
    VEVE(i, 0, 4) if (not ccs[i].empty()) {
        if (not quad[i]) {
          quad[i] = Alloc(i == 1 or i == 2 ? x1 : xm,
                          i >= 2 ? y1 : ym,
                          i == 1 or i == 2 ? xm : x2,
                          i >= 2 ? ym : y2);
        }
        pool[quad[i]].Insert(ccs[i]);
      }
  }

  void Erase(const Circle& c, const vector<Circle>& circs, vector<int>& res) {
    static vector<int> temp;
//    if (x1 + 1 == x2 or c.Contains(x1, y1, x2, y2)) {
//      DEBUG(c.x, c.y, c.r, x1, y1, x2, y2, ids);
    temp.clear();
    RARA(id, ids) {
      if (res[id] != -(SIZE(circs) + 1)) {
      } else if (c.Intersects(circs[id])) {
        res[id] = c.id;
      } else {
        temp.push_back(id);
      }
    }
    ids.swap(temp);
//    }
    RARA(qq, quad) {
      Node* q = pool + qq;
      if (qq and c.Intersects(q->x1, q->y1, q->x2, q->y2)) {
        q->Erase(c, circs, res);
      }
    }
  }
};

Node Node::pool[12000000];
int Node::next_node = 1;

void Solve(ll) {
//  DEBUG(sizeof(Node::pool));
  int n;
  n = next_int();
//  cin >> n;
  vector<Circle> circs(n);
  vector<int> res(n, -(n + 1));
  {
    map<tuple<int, int, int>, int> was;
    VEVE(i, 0, n) {
      auto& c = circs[i];
      c.x = next_int();
      c.y = next_int();
      c.r = next_int();
//      cin >> c.x >> c.y >> c.r;
      c.id = i;
      int& w = was[make_tuple(c.x, c.y, c.r)];
      if (w > 0) {
        res[i] = -w;
      } else {
        w = i + 1;
      }
    }
  }
  const int PW = 1 << 30;
  Node* root = Node::pool + Node::Alloc(-PW, -PW, PW, PW);
  vector<int> ord(n);
  iota(ALL(ord), 0);
  sort(ALL(ord), [&](int a, int b) {
    return circs[a] < circs[b];
  });
  set<int> rem_ids;
  VEVE(i, 0, n) if (res[ord[i]] == -(n + 1)) rem_ids.insert(i);
  VEVE(its, 0, min(n, (int) (1e7) / n)) {
    if (rem_ids.empty())
      break;
    const auto& c = circs[ord[*rem_ids.begin()]];
    for (auto it = rem_ids.begin(); it != rem_ids.end();) {
      if (c.Intersects(circs[ord[*it]])) {
        res[ord[*it]] = c.id;
        rem_ids.erase(it++);
      } else {
        ++it;
      }
    }
  }
  vector<Circle> rem;
  rem.reserve(n);
  RARA(i, rem_ids) {
    rem.push_back(circs[ord[i]]);
//    DEBUG(i + 1);
  }
  root->Insert(rem);
  RARA(c, rem) if (res[c.id] == -(n + 1)) {
      root->Erase(c, circs, res);
    }
  RARA(r, res) if (r < 0) r = res[-r - 1];
  RARA(r, res) {
//    cout << (r + 1) << ' ';
    write_int(r + 1);
    write_char(' ');
  }
//  cout << endl;
  write_char('\n');
  write_flush();
}

void Init() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
}

int32_t

main() {
#ifdef AZN
  freopen("input.txt", "r", stdin);
#endif
  Init();
  ll tests = 1;
  VEVE(test, 1, tests + 1) Solve(test);
  return 0;
}

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