oj.uz

Submission #966719

# Submission time Handle Problem Language Result Execution time Memory
966719 2024-04-20T08:59:10 Z Soumya1 Circle selection (APIO18_circle_selection) C++17
19 / 100
 3000 ms 608432 KB 
#include <bits/stdc++.h>
using namespace std;
const int mxN = 3e5 + 5;
int x[mxN], y[mxN], r[mxN], ans[mxN];
bool intersect(int a, int b) {
  return 1LL * (x[a] - x[b]) * (x[a] - x[b]) + 1LL * (y[a] - y[b]) * (y[a] - y[b]) <= 1LL * (r[a] + r[b]) * (r[a] + r[b]);
}
int block;
map<pair<int, int>, vector<int>> mp;
int n;
void scale() {
  mp.clear();
  for (int i = 0; i < n; i++) {
    if (ans[i]) continue;
    mp[{x[i] / block, y[i] / block}].push_back(i);
  }
}
void testCase() {
  cin >> n;
  vector<int> all;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> y[i] >> r[i];
  }
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 0);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    if (r[i] != r[j]) return r[i] > r[j];
    return i < j;
  });
  block = r[ord[0]];
  scale();
  for (int i : ord) {
    if (ans[i]) continue;
    if (2 * r[i] < block) {
      block = 2 * r[i];
      scale();
    }
    for (int xx = x[i] / block - 2; xx <= x[i] / block + 2; xx++) {
      for (int yy = y[i] / block - 2; yy <= y[i] / block + 2; yy++) {
        auto &v = mp[{xx, yy}];
        for (int j = 0; j < v.size(); ) {
          if (intersect(i, v[j])) {
            ans[v[j]] = i + 1;
            swap(v[j], v.back());
            v.pop_back();
          } else {
            j++;
          }
        }
      }
    }
  }
  for (int i = 0; i < n; i++) cout << ans[i] << " ";
  cout << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Compilation message

circle_selection.cpp: In function 'void testCase()':
circle_selection.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int j = 0; j < v.size(); ) {
      |                         ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4560 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4576 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4556 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 3 ms 4700 KB Output is correct
20 Correct 3 ms 4700 KB Output is correct
21 Correct 3 ms 4700 KB Output is correct
22 Correct 468 ms 9820 KB Output is correct
23 Correct 382 ms 9812 KB Output is correct
24 Correct 504 ms 9984 KB Output is correct
25 Correct 404 ms 9820 KB Output is correct
26 Correct 479 ms 10032 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 15160 KB Output is correct
2 Correct 121 ms 16312 KB Output is correct
3 Correct 115 ms 16064 KB Output is correct
4 Correct 110 ms 15168 KB Output is correct
5 Correct 190 ms 17388 KB Output is correct
6 Correct 1211 ms 86996 KB Output is correct
7 Correct 323 ms 21844 KB Output is correct
8 Correct 410 ms 32452 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4560 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4576 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4556 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 3 ms 4700 KB Output is correct
20 Correct 3 ms 4700 KB Output is correct
21 Correct 3 ms 4700 KB Output is correct
22 Correct 468 ms 9820 KB Output is correct
23 Correct 382 ms 9812 KB Output is correct
24 Correct 504 ms 9984 KB Output is correct
25 Correct 404 ms 9820 KB Output is correct
26 Correct 479 ms 10032 KB Output is correct
27 Correct 6 ms 4956 KB Output is correct
28 Correct 4 ms 4824 KB Output is correct
29 Correct 5 ms 4956 KB Output is correct
30 Correct 1907 ms 15360 KB Output is correct
31 Correct 2011 ms 15348 KB Output is correct
32 Correct 1734 ms 15412 KB Output is correct
33 Correct 39 ms 9280 KB Output is correct
34 Correct 40 ms 9528 KB Output is correct
35 Correct 61 ms 8780 KB Output is correct
36 Execution timed out 3018 ms 112896 KB Time limit exceeded
37 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4560 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4576 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4556 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 3 ms 4700 KB Output is correct
20 Correct 3 ms 4700 KB Output is correct
21 Correct 3 ms 4700 KB Output is correct
22 Correct 468 ms 9820 KB Output is correct
23 Correct 382 ms 9812 KB Output is correct
24 Correct 504 ms 9984 KB Output is correct
25 Correct 404 ms 9820 KB Output is correct
26 Correct 479 ms 10032 KB Output is correct
27 Correct 113 ms 15160 KB Output is correct
28 Correct 121 ms 16312 KB Output is correct
29 Correct 115 ms 16064 KB Output is correct
30 Correct 110 ms 15168 KB Output is correct
31 Correct 190 ms 17388 KB Output is correct
32 Correct 1211 ms 86996 KB Output is correct
33 Correct 323 ms 21844 KB Output is correct
34 Correct 410 ms 32452 KB Output is correct
35 Correct 1 ms 4444 KB Output is correct
36 Execution timed out 3075 ms 110820 KB Time limit exceeded
37 Halted 0 ms 0 KB -