oj.uz

Submission #316902

# Submission time Handle Problem Language Result Execution time Memory
316902 2020-10-28T14:25:14 Z casperwang Circle selection (APIO18_circle_selection) C++14
15 / 100
 589 ms 43716 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define int 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;
  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 (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];
}

Compilation message

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:42:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Cir>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < cir.size(); i++)
      |                     ~~^~~~~~~~~~~~
circle_selection.cpp:55:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if (p == arr.size() || arr[p].ff.ff != i) continue;
      |             ~~^~~~~~~~~~~~~
circle_selection.cpp:56:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         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 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 31508 KB Output is correct
2 Incorrect 219 ms 31424 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 1 ms 384 KB Output is correct
2 Correct 164 ms 10276 KB Output is correct
3 Correct 558 ms 32064 KB Output is correct
4 Correct 561 ms 32064 KB Output is correct
5 Correct 547 ms 35584 KB Output is correct
6 Correct 228 ms 18040 KB Output is correct
7 Correct 106 ms 9056 KB Output is correct
8 Correct 18 ms 2168 KB Output is correct
9 Correct 589 ms 36188 KB Output is correct
10 Correct 530 ms 43716 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 31604 KB Output is correct
2 Correct 425 ms 31424 KB Output is correct
3 Incorrect 335 ms 31424 KB Output isn't correct
4 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 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 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 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 0 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -