oj.uz

Submission #49846

# Submission time Handle Problem Language Result Execution time Memory
49846 2018-06-03T19:22:54 Z zemen Circle selection (APIO18_circle_selection) C++17
0 / 100
 3000 ms 74724 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define int ll

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].empty()) {
    return inf;
  }
  //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);
  vector<Circle> bad;
  for (auto& c : cs) {
    int killed = inf;
    for (auto& c2 : bad) {
      if (c2.intersects(c)) {
        killed = min(killed, c2.id);
      }
    }
    if (killed == inf) {
      killed = c.id;
      bad.push_back(c);
    }
    res[c.id] = killed;
  }

  //for (auto& c : cs) {
    //int id = lookup(c);
    //if (id == inf) {
      //turn_on(c.id);
      //cerr << "on " << c.id+1 << '\n';
      //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 45 ms 57720 KB Output is correct
2 Correct 54 ms 57956 KB Output is correct
3 Correct 44 ms 57956 KB Output is correct
4 Correct 43 ms 57972 KB Output is correct
5 Correct 53 ms 58032 KB Output is correct
6 Correct 46 ms 58032 KB Output is correct
7 Correct 46 ms 58064 KB Output is correct
8 Correct 50 ms 58064 KB Output is correct
9 Incorrect 45 ms 58064 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 74572 KB Output is correct
2 Incorrect 536 ms 74708 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 74708 KB Output is correct
2 Execution timed out 3028 ms 74708 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3034 ms 74724 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 57720 KB Output is correct
2 Correct 54 ms 57956 KB Output is correct
3 Correct 44 ms 57956 KB Output is correct
4 Correct 43 ms 57972 KB Output is correct
5 Correct 53 ms 58032 KB Output is correct
6 Correct 46 ms 58032 KB Output is correct
7 Correct 46 ms 58064 KB Output is correct
8 Correct 50 ms 58064 KB Output is correct
9 Incorrect 45 ms 58064 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 57720 KB Output is correct
2 Correct 54 ms 57956 KB Output is correct
3 Correct 44 ms 57956 KB Output is correct
4 Correct 43 ms 57972 KB Output is correct
5 Correct 53 ms 58032 KB Output is correct
6 Correct 46 ms 58032 KB Output is correct
7 Correct 46 ms 58064 KB Output is correct
8 Correct 50 ms 58064 KB Output is correct
9 Incorrect 45 ms 58064 KB Output isn't correct
10 Halted 0 ms 0 KB -