oj.uz

Submission #959521

# Submission time Handle Problem Language Result Execution time Memory
959521 2024-04-08T11:38:20 Z rxlfd314 Circle selection (APIO18_circle_selection) C++17
15 / 100
 1478 ms 24660 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ari2=array<int,2>;
using ari3=array<int,3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for (int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N;
  cin >> N;
  vt<int> X(N), Y(N), R(N);
  FOR(i, 0, N-1)
    cin >> X[i] >> Y[i] >> R[i];
  vt<int> ord(N);
  iota(all(ord), 0);
  sort(all(ord), [&](const int &a, const int &b) {
    return ari2{R[a], b} > ari2{R[b], a};   
  });
  auto good = [&](int i, int j) {
    auto sq = [&](int x) {
      return 1ll * x * x;
    };  
    return sq(X[i]-X[j]) + sq(Y[i]-Y[j]) <= sq(R[i]+R[j]);
  };
  vt<int> ans(N, -1);
  for (int r=1<<30; r>0; r>>=1) {
    vt<ari3> points;
    FOR(i, 0, N-1)
      if (ans[i] < 0)
        points.push_back({X[i]/r, Y[i]/r, i});
    sort(all(points));
    for (int i : ord) {
      if (ans[i]>=0 || R[i] < r/2 || R[i] > r)
        continue;
      ans[i] = i;
      int x = X[i] / r;
      int y = Y[i] / r;
      FOR(d, -2, 2)
        FOR(j, lower_bound(all(points), ari3{x+d, y-2, 0}) - begin(points), size(points)-1) {
          auto [xj, yj, ij] = points[j];
          if (xj != x+d || abs(yj-y) > 2)
            break;
          if (good(i, ij))
            ans[ij] = i;
        }
    }
  }
  FOR(i, 0, N-1)
    cout << (ans[i]<0 ? i : ans[i]) + 1 << "\n "[i+1<N];
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 22528 KB Output is correct
2 Incorrect 231 ms 22576 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 0 ms 348 KB Output is correct
2 Correct 274 ms 7920 KB Output is correct
3 Correct 1010 ms 24432 KB Output is correct
4 Correct 1000 ms 24188 KB Output is correct
5 Correct 887 ms 23804 KB Output is correct
6 Correct 426 ms 12808 KB Output is correct
7 Correct 217 ms 6968 KB Output is correct
8 Correct 41 ms 1844 KB Output is correct
9 Correct 1026 ms 24268 KB Output is correct
10 Correct 823 ms 24660 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 23892 KB Output is correct
2 Correct 1478 ms 23252 KB Output is correct
3 Incorrect 569 ms 24652 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -