oj.uz

Submission #49843

# Submission time Handle Problem Language Result Execution time Memory
49843 2018-06-03T19:00:27 Z zemen Circle selection (APIO18_circle_selection) C++17
38 / 100
 1668 ms 167128 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

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

  static ll sqr(ll x) {
    return x * x;
  }

  bool intersects(const Circle& c) const {
    return sqr(c.x - x) + sqr(c.y - y) <= sqr(r + c.r);
  }
};
istream& operator>>(istream& in, Circle& c) {
  return in >> c.x >> c.y >> c.r;
}

const ll infl = 1e18 + 7;

struct Bbox {
  ll xl, xr, yl, yr;

  Bbox() : xl(infl), xr(-infl), yl(infl), yr(-infl) {
  }

  void add(const Circle& c) {
    xl = min<ll>(xl, c.x - c.r);
    xr = max<ll>(xr, c.x + c.r);
    yl = min<ll>(yl, c.y - c.r);
    yr = max<ll>(yr, c.y + c.r);
  }

  bool intersects(const Circle& c) const {
    if (empty()) {
      return false;
    }
    if (c.x - c.r > xr || c.x + c.r < xl) {
      return false;
    }
    if (c.y - c.r > yr || c.y + c.r < yl) {
      return false;
    }
    return true;
  }

  bool empty() const {
    return xl == infl;
  }
};

const int base = 1 << 19;
vector<Circle> t[base * 2];
Bbox box[base * 2];
int endv[base];

bool cmpx(const Circle& a, const Circle& b) {
  return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool cmpy(const Circle& a, const Circle& b) {
  return a.y < b.y || (a.y == b.y && a.x < b.x);
}

bool cmpr(const Circle& a, const Circle& b) {
  return a.r > b.r || (a.r == b.r && a.id < b.id);
}

void build(int v, bool byx) {
  assert(!t[v].empty());
  sort(t[v].begin(), t[v].end(), byx ? cmpx : cmpy);
  if (t[v].size() == 1) {
    endv[t[v][0].id] = v;
    return;
  }
  int n = (int) t[v].size();
  t[v * 2].insert(t[v * 2].end(), t[v].begin(), t[v].begin() + n / 2);
  t[v * 2 + 1].insert(t[v * 2 + 1].end(), t[v].begin() + n / 2, t[v].end());
  build(v * 2, !byx);
  build(v * 2 + 1, !byx);
}

const int inf = 1e9;
int lookup(const Circle& c, int v = 1) {
  if (!box[v].intersects(c)) {
    return inf;
  }
  if (t[v].size() == 1) {
    if (t[v][0].intersects(c)) {
      return t[v][0].id;
    } else {
      return inf;
    }
  }
  return min(lookup(c, v * 2), lookup(c, v * 2 + 1));
}

void turn_on(int id) {
  int v = endv[id];
  const Circle& c = t[v][0];
  while (v >= 1) {
    box[v].add(c);
    v /= 2;
  }
}

signed main() {
#ifdef LOCAL
  assert(freopen("b.in", "r", stdin));
#endif
  int n;
  cin >> n;
  vector<Circle> cs;
  for (int i = 0; i < n; ++i) {
    Circle c;
    cin >> c;
    c.id = i;
    t[1].push_back(c);
    cs.push_back(c);
  }
  build(1, true);
  sort(cs.begin(), cs.end(), cmpr);
  vector<int> res(n);
  for (auto& c : cs) {
    int id = lookup(c);
    if (id == inf) {
      turn_on(c.id);
      id = c.id;
    }
    res[c.id] = id;
  }
  for (int x : res) {
    cout << x + 1 << ' ';
  }
  cout << '\n';
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 57720 KB Output is correct
2 Correct 44 ms 57828 KB Output is correct
3 Correct 43 ms 57904 KB Output is correct
4 Correct 42 ms 57980 KB Output is correct
5 Correct 43 ms 57980 KB Output is correct
6 Correct 43 ms 58016 KB Output is correct
7 Correct 43 ms 58016 KB Output is correct
8 Correct 57 ms 58020 KB Output is correct
9 Incorrect 46 ms 58020 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1095 ms 166952 KB Output is correct
2 Incorrect 1183 ms 167056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 167056 KB Output is correct
2 Correct 541 ms 167056 KB Output is correct
3 Correct 1668 ms 167056 KB Output is correct
4 Correct 1591 ms 167056 KB Output is correct
5 Correct 1450 ms 167056 KB Output is correct
6 Correct 810 ms 167056 KB Output is correct
7 Correct 419 ms 167056 KB Output is correct
8 Correct 104 ms 167056 KB Output is correct
9 Correct 1489 ms 167060 KB Output is correct
10 Correct 1474 ms 167060 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 167060 KB Output is correct
2 Correct 1384 ms 167128 KB Output is correct
3 Correct 1520 ms 167128 KB Output is correct
4 Correct 1388 ms 167128 KB Output is correct
5 Correct 1373 ms 167128 KB Output is correct
6 Correct 1519 ms 167128 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 57720 KB Output is correct
2 Correct 44 ms 57828 KB Output is correct
3 Correct 43 ms 57904 KB Output is correct
4 Correct 42 ms 57980 KB Output is correct
5 Correct 43 ms 57980 KB Output is correct
6 Correct 43 ms 58016 KB Output is correct
7 Correct 43 ms 58016 KB Output is correct
8 Correct 57 ms 58020 KB Output is correct
9 Incorrect 46 ms 58020 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 57720 KB Output is correct
2 Correct 44 ms 57828 KB Output is correct
3 Correct 43 ms 57904 KB Output is correct
4 Correct 42 ms 57980 KB Output is correct
5 Correct 43 ms 57980 KB Output is correct
6 Correct 43 ms 58016 KB Output is correct
7 Correct 43 ms 58016 KB Output is correct
8 Correct 57 ms 58020 KB Output is correct
9 Incorrect 46 ms 58020 KB Output isn't correct
10 Halted 0 ms 0 KB -