oj.uz

Submission #399813

# Submission time Handle Problem Language Result Execution time Memory
399813 2021-05-06T16:53:11 Z my99n Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 62724 KB 
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<long long,long long> point;
 
struct A {
  long long x, y, r;
  int i;
  bool operator < (const A & o) const {
    if (r == o.r) return i < o.i;
    return r > o.r;
  }
} ori[300100], cir[300100];
 
struct X {
  long long x;
  int i, t;
  bool operator < (const X & o) const {
    if (x == o.x) return i < o.i;
    return x < o.x;
  }
};

set<X> sx;
 
int ans[300100];
 
long long dis (point i, point j) {
  long long temp = ((i.x-j.x) * (i.x-j.x)) + ((i.y-j.y) * (i.y-j.y));
  return temp;
}
 
bool intersect (A i, A j) {
  return (dis({i.x, i.y}, {j.x, j.y}) <= (i.r+j.r)*(i.r+j.r));
}

bool cover (A i, long long x, long long y) {
  return intersect(i, {x, y, 0, -1});
}
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    long long x, y, r; cin >> x >> y >> r;
    ori[i] = cir[i] = {x, y, r, i};
    sx.insert({x+r, i, 1});
    sx.insert({x-r, i, 0});
  }
  sort(cir+1, cir+1+n);

  // for (auto x : sx) {
  //   cerr << x.i << ' ' << x.t << endl;
  // }
 
  for (int i = 1; i <= n; i++) {
    int ind = cir[i].i;
    cerr << ind << endl;
    if (ans[ind]) continue;
    auto a = sx.lower_bound({ori[ind].x, ind, -1});
    cerr << "a " << a->x << ' ' << a->i << ' ' << a->t << endl;
    if (a != sx.begin()) {
      auto x = prev(a);
      while (x != sx.begin()) {
        // cerr  << "x " << x->x << ' ' << x->i << ' ' << x->t << endl;
        if (ans[x->i] != 0) {
          auto temp = x--;
          sx.erase(temp);
          continue;
        }
        // cerr  << "x " << x->x << ' ' << x->i << ' ' << x->t << endl;
        if (!intersect(ori[ind], ori[x->i])) break;
        // cerr << "ans " << x->i << ' ' << ind << endl;
        ans[x->i] = ind;
        auto temp = x--;
        sx.erase(temp);
      }
      if (x == sx.begin() and cover(ori[ind], ori[x->i].x, ori[x->i].y)) {
        if (!ans[x->i]) ans[x->i] = ind;
        // cerr << "ans " << x->i << ' ' << ind << endl;
        auto temp = x;
        sx.erase(temp);
      }
    }
    auto x = a;
    while (x != sx.end()) {
      // cerr  << "x " << x->x << ' ' << x->i << ' ' << x->t << endl;
      if (ans[x->i] != 0) {
        auto temp = x++;
        sx.erase(temp);
        continue;
      }
      // cerr  << "x " << x->x << ' ' << x->i << ' ' << x->t << endl;
      if (!cover(ori[ind], ori[x->i].x, ori[x->i].y)) break;
      ans[x->i] = ind;
      // cerr << "ans " << x->i << ' ' << ind << endl;
      auto temp = x++;
      sx.erase(temp);
    }
  }
 
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << ' ';
  } cout << endl;
  return 0;
}
/*
11 
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1581 ms 62724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -