Submission #539217

#	Time	Username	Problem	Language	Result	Execution time	Memory
539217		cadmiumsky	Circle selection (APIO18_circle_selection)	C++17	57 / 100	2214 ms	94028 KiB

circle_selection

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

namespace Cercus {
  unordered_map<int, unordered_map<int, vector<int> > > cont;
  int lastr = 2e9 + 5;
  vector<tuple<int, int, int> > v;
  vector<int> sorted, elim;
  int xx[2], yy[2], rr[2];
  ll p2(ll x) { return x * x; }
  bool check(int i, int j) {
    tie(rr[0], xx[0], yy[0]) = v[i];
    tie(rr[1], xx[1], yy[1]) = v[j];
    return p2(xx[0] - xx[1]) + p2(yy[0] - yy[1]) <= p2(rr[0] + rr[1]);
  }
  void redocontainer(int nr) {
    lastr = nr;
    for(int i = 0, x, y, r; i < v.size(); i++) {
      if(elim[i] == -1) {
        tie(r, x, y) = v[i];
        cont[x / (2 * nr)][y / (2 * nr)].push_back(i);
      }
    }
  }
  void gothrough(int ind) {
    if(elim[ind] != -1)
      return;
    int x, y, r;
    tie(r, x, y) = v[ind];
    if(r <= lastr / 2)
      redocontainer(r);
    x /= 2 * lastr;
    y /= 2 * lastr;
    //cerr << "--" << lastr << "--\n";
    for(int i = x - 1; i <= x + 1; i++) {
      if(cont.find(i) == cont.end())
        continue;
      for(int j = y - 1; j <= y + 1; j++) {
        if(cont[i].find(j) == cont[i].end())
          continue;
        for(int ptr = 0, z; ptr < cont[i][j].size(); ptr++) {
          z = cont[i][j][ptr];
          //cerr << ind + 1<< "--> " << z + 1 << ' ';
          if(check(z, ind)) {
            //cerr << "YES";
            elim[z] = ind;
            swap(cont[i][j].back(), cont[i][j][ptr]);
            cont[i][j].pop_back();
            ptr--;
          }
          //cerr << '\n';
        }
      }
    }
  }
  void read() {
    int n;
    cin >> n;
    v.resize(n);
    sorted.resize(n);
    elim.resize(n);
    for(auto &[r, x, y] : v)
      cin >> x >> y >> r;
    for(int i = 0; i < n; i++)
      sorted[i] = i, elim[i] = -1;
    sort(sorted.begin(), sorted.end(), [&](auto x, auto y) { return get<0>(v[x]) > get<0>(v[y]) || (get<0>(v[x]) == get<0>(v[y]) && x < y);});
  }
  void startelim() {
    for(auto z : sorted)
      gothrough(z);
  }
  void print() {
    for(auto x : elim)
      cout << x + 1 << ' ';
    cout << '\n';
    return;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  Cercus::read();
  Cercus::startelim();
  Cercus::print();
}

Compilation message (stderr)

circle_selection.cpp: In function 'void Cercus::redocontainer(int)':
circle_selection.cpp:20:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0, x, y, r; i < v.size(); i++) {
      |                             ~~^~~~~~~~~~
circle_selection.cpp: In function 'void Cercus::gothrough(int)':
circle_selection.cpp:43:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int ptr = 0, z; ptr < cont[i][j].size(); ptr++) {
      |                             ~~~~^~~~~~~~~~~~~~~~~~~

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