oj.uz

Submission #959523

# Submission time Handle Problem Language Result Execution time Memory
959523 2024-04-08T11:40:51 Z rxlfd314 Circle selection (APIO18_circle_selection) C++17
15 / 100
 1441 ms 26196 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], assert(ans[i] >= 0);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 0 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 24988 KB Output is correct
2 Incorrect 229 ms 23968 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 344 KB Output is correct
2 Correct 277 ms 7916 KB Output is correct
3 Correct 1010 ms 24916 KB Output is correct
4 Correct 996 ms 24916 KB Output is correct
5 Correct 869 ms 25168 KB Output is correct
6 Correct 419 ms 12636 KB Output is correct
7 Correct 211 ms 6840 KB Output is correct
8 Correct 41 ms 1844 KB Output is correct
9 Correct 1040 ms 26196 KB Output is correct
10 Correct 819 ms 24060 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1075 ms 25920 KB Output is correct
2 Correct 1441 ms 23076 KB Output is correct
3 Incorrect 550 ms 25124 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 0 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 0 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 0 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 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -