oj.uz

Submission #316905

# Submission time Handle Problem Language Result Execution time Memory
316905 2020-10-28T14:32:43 Z casperwang Circle selection (APIO18_circle_selection) C++14
0 / 100
 3000 ms 16108 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define ppi pair<pii,int>
#define ff first
#define ss second
using namespace std;

const int MAXN = 300000;

struct Cir{
  int x, y, r, id;
  Cir() {}
  Cir(int _x, int _y, int _r, int _id) {
    x = _x, y = _y, r = _r, id = _id;
  }
};

bool intersect(const Cir &a, const Cir &b) {
  return (ll)(a.x-b.x)*(a.x-b.x)+(ll)(a.y-b.y)*(a.y-b.y) <= (ll)(a.r+b.r)*(a.r+b.r);
}

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  vector <Cir> cir, tmp;
  for (int i = 0; i < n; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    cir.pb(Cir(x, y, r, i+1));
  }
  sort(cir.begin(), cir.end(), [](const Cir a, const Cir b){
      return a.r != b.r ? a.r > b.r : a.id < b.id;
      });
  int now_r = cir[0].r+1;
  vector <int> ans(n+1);
  while (cir.size()) {
    vector <ppi> arr;
    for (int i = 0; i < cir.size(); i++)
      arr.pb(ppi(pii(cir[i].x / now_r, cir[i].y / now_r), i));
    sort(arr.begin(), arr.end());
    for (Cir C : cir) {
      if (ans[C.id]) continue;
      if (C.r < now_r/2) break;
      int X = C.x / now_r, Y = C.y / now_r;
      ppi grid;
      grid.ss = 0;
      grid.ff.ss = Y-2;
      for (int i = X-2; i <= X+2; i++) {
        grid.ff.ff = i;
        int p = lower_bound(arr.begin(), arr.end(), grid) - arr.begin();
        if (p == arr.size() || arr[p].ff.ff != i) continue;
        while (p < arr.size() && arr[p].ff.ff == i && arr[p].ff.ss <= Y+2) {
          if (ans[cir[arr[p].ss].id]) continue;
          if (intersect(C, cir[arr[p].ss]))
            ans[cir[arr[p].ss].id] = C.id;
          p++;
        }
      }
    }
    arr.clear();
    for (Cir C : cir)
      if (!ans[C.id]) tmp.pb(C);
    cir = tmp;
    tmp.clear();
    now_r /= 2;
  }
  for (int i = 1; i <= n; i++)
    cout << ans[i] << " \n"[i==n];
  return 0;
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Cir>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < cir.size(); i++)
      |                     ~~^~~~~~~~~~~~
circle_selection.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if (p == arr.size() || arr[p].ff.ff != i) continue;
      |             ~~^~~~~~~~~~~~~
circle_selection.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         while (p < arr.size() && arr[p].ff.ff == i && arr[p].ff.ss <= Y+2) {
      |                ~~^~~~~~~~~~~~

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 15840 KB Output is correct
2 Execution timed out 3075 ms 15828 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 16108 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 384 KB Output is correct
2 Execution timed out 3046 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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