oj.uz

Submission #981957

# Submission time Handle Problem Language Result Execution time Memory
981957 2024-05-13T17:14:56 Z xiaowuc1 Circle selection (APIO18_circle_selection) C++17
100 / 100
 1971 ms 52144 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(0) cerr
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << flush;
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template<class T>
bool updmin(T& a, T b) {
  if(b < a) {
    a = b;
    return true;
  }
  return false;
}
template<class T>
bool updmax(T& a, T b) {
  if(b > a) {
    a = b;
    return true;
  }
  return false;
}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

void solve() {
  int n;
  cin >> n;
  vector<array<ll, 4>> circles(n);
  vector<array<ll, 3>> meta(n);
  auto touch = [&](int i, int j) {
    ll x = meta[i][0] - meta[j][0];
    ll y = meta[i][1] - meta[j][1];
    ll r = meta[i][2] + meta[j][2];
    return x*x+y*y <= r*r;
  };
  for(int i = 0; i < n; i++) {
    ll x, y, r;
    cin >> x >> y >> r;
    x += 2e9;
    y += 2e9;
    assert(x >= r);
    assert(y >= r);
    circles[i] = {x, y, r, i};
    meta[i] = {x, y, r};
  }
  sort(all(circles), [&](auto a, auto b) -> bool {
    if(a[2] != b[2]) return a[2] > b[2];
    return a[3] < b[3];
  });
  vector<int> ret(n, -1);
  vector<bool> gone(n);
  int CIRCLE_SIZE = 1 << 30;
  bool dirty = false;
  vector<array<ll, 2>> coords;
  vector<vector<int>> locs;
  for(auto circ: circles) {
    if(gone[circ[3]]) continue;
    while(CIRCLE_SIZE > circ[2]) {
      CIRCLE_SIZE /= 2;
      dirty = true;
    }
    if(dirty) {
      coords.clear();
      locs.clear();
      for(int i = 0; i < n; i++) {
        if(gone[i]) continue;
        auto [x, y, r] = meta[i];
        ll xl = x;
        ll yl = y;
        xl /= CIRCLE_SIZE;
        yl /= CIRCLE_SIZE;
        coords.pb({xl, yl});
      }
      sort(all(coords));
      coords.erase(unique(all(coords)), coords.end());
      locs.resize(sz(coords));
      for(int i = 0; i < n; i++) {
        if(gone[i]) continue;
        auto [x, y, r] = meta[i];
        ll xl = x;
        ll yl = y;
        xl /= CIRCLE_SIZE;
        yl /= CIRCLE_SIZE;
        int tidx = lb(all(coords), array<ll, 2>({xl, yl})) - coords.begin();
        assert(tidx < sz(coords));
        assert(coords[tidx][0] == xl);
        assert(coords[tidx][1] == yl);
        locs[tidx].pb(i);
      }
      dirty = false;
    }
    auto [x, y, r, idx] = circ;
    assert(!gone[idx]);
    ret[idx] = idx;
    gone[idx] = true;
    ll xl = x-r, xr = x+r;
    ll yl = y-r, yr = y+r;
    xl /= CIRCLE_SIZE, yl /= CIRCLE_SIZE;
    xr /= CIRCLE_SIZE, yr /= CIRCLE_SIZE;
    for(ll a = xl-2; a <= xr+2; a++) for(ll b = yl-2; b <= yr+2; b++) {
      int tidx = lb(all(coords), array<ll, 2>({a, b})) - coords.begin();
      if(tidx == sz(coords) || coords[tidx] != array<ll, 2>({a, b})) continue;
      vector<int> nv;
      for(auto out: locs[tidx]) {
        if(gone[out]) continue;
        if(!touch(idx, out)) {
          nv.pb(out);
        }
        else {
          gone[out] = true;
          ret[out] = idx;
        }
      }
      if(sz(nv)) swap(locs[tidx], nv);
    }
  }
  for(int i = 0; i < n; i++) cout << ++ret[i] << " \n"[i == n-1];
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 588 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 452 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct
20 Correct 3 ms 1116 KB Output is correct
21 Correct 3 ms 1116 KB Output is correct
22 Correct 16 ms 1116 KB Output is correct
23 Correct 20 ms 1112 KB Output is correct
24 Correct 17 ms 1108 KB Output is correct
25 Correct 16 ms 1256 KB Output is correct
26 Correct 17 ms 1256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 34480 KB Output is correct
2 Correct 152 ms 34736 KB Output is correct
3 Correct 141 ms 35348 KB Output is correct
4 Correct 151 ms 35136 KB Output is correct
5 Correct 215 ms 32188 KB Output is correct
6 Correct 634 ms 39416 KB Output is correct
7 Correct 286 ms 34484 KB Output is correct
8 Correct 340 ms 34224 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 497 ms 16672 KB Output is correct
3 Correct 1674 ms 51012 KB Output is correct
4 Correct 1709 ms 49412 KB Output is correct
5 Correct 1482 ms 52144 KB Output is correct
6 Correct 541 ms 27152 KB Output is correct
7 Correct 250 ms 14276 KB Output is correct
8 Correct 37 ms 3124 KB Output is correct
9 Correct 1721 ms 50356 KB Output is correct
10 Correct 1228 ms 50356 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1343 ms 50352 KB Output is correct
2 Correct 1032 ms 49836 KB Output is correct
3 Correct 405 ms 43168 KB Output is correct
4 Correct 1228 ms 48864 KB Output is correct
5 Correct 1436 ms 49784 KB Output is correct
6 Correct 249 ms 37516 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 588 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 452 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct
20 Correct 3 ms 1116 KB Output is correct
21 Correct 3 ms 1116 KB Output is correct
22 Correct 16 ms 1116 KB Output is correct
23 Correct 20 ms 1112 KB Output is correct
24 Correct 17 ms 1108 KB Output is correct
25 Correct 16 ms 1256 KB Output is correct
26 Correct 17 ms 1256 KB Output is correct
27 Correct 8 ms 1628 KB Output is correct
28 Correct 5 ms 1744 KB Output is correct
29 Correct 5 ms 1624 KB Output is correct
30 Correct 45 ms 2024 KB Output is correct
31 Correct 37 ms 2024 KB Output is correct
32 Correct 34 ms 2004 KB Output is correct
33 Correct 53 ms 12444 KB Output is correct
34 Correct 50 ms 12156 KB Output is correct
35 Correct 58 ms 11992 KB Output is correct
36 Correct 472 ms 16264 KB Output is correct
37 Correct 462 ms 16532 KB Output is correct
38 Correct 456 ms 16576 KB Output is correct
39 Correct 470 ms 14144 KB Output is correct
40 Correct 403 ms 14148 KB Output is correct
41 Correct 414 ms 14028 KB Output is correct
42 Correct 181 ms 15524 KB Output is correct
43 Correct 410 ms 16332 KB Output is correct
44 Correct 399 ms 16336 KB Output is correct
45 Correct 398 ms 16328 KB Output is correct
46 Correct 406 ms 16584 KB Output is correct
47 Correct 446 ms 16464 KB Output is correct
48 Correct 413 ms 16332 KB Output is correct
49 Correct 408 ms 16608 KB Output is correct
50 Correct 456 ms 16456 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 588 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 452 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct
20 Correct 3 ms 1116 KB Output is correct
21 Correct 3 ms 1116 KB Output is correct
22 Correct 16 ms 1116 KB Output is correct
23 Correct 20 ms 1112 KB Output is correct
24 Correct 17 ms 1108 KB Output is correct
25 Correct 16 ms 1256 KB Output is correct
26 Correct 17 ms 1256 KB Output is correct
27 Correct 150 ms 34480 KB Output is correct
28 Correct 152 ms 34736 KB Output is correct
29 Correct 141 ms 35348 KB Output is correct
30 Correct 151 ms 35136 KB Output is correct
31 Correct 215 ms 32188 KB Output is correct
32 Correct 634 ms 39416 KB Output is correct
33 Correct 286 ms 34484 KB Output is correct
34 Correct 340 ms 34224 KB Output is correct
35 Correct 1 ms 344 KB Output is correct
36 Correct 497 ms 16672 KB Output is correct
37 Correct 1674 ms 51012 KB Output is correct
38 Correct 1709 ms 49412 KB Output is correct
39 Correct 1482 ms 52144 KB Output is correct
40 Correct 541 ms 27152 KB Output is correct
41 Correct 250 ms 14276 KB Output is correct
42 Correct 37 ms 3124 KB Output is correct
43 Correct 1721 ms 50356 KB Output is correct
44 Correct 1228 ms 50356 KB Output is correct
45 Correct 1343 ms 50352 KB Output is correct
46 Correct 1032 ms 49836 KB Output is correct
47 Correct 405 ms 43168 KB Output is correct
48 Correct 1228 ms 48864 KB Output is correct
49 Correct 1436 ms 49784 KB Output is correct
50 Correct 249 ms 37516 KB Output is correct
51 Correct 8 ms 1628 KB Output is correct
52 Correct 5 ms 1744 KB Output is correct
53 Correct 5 ms 1624 KB Output is correct
54 Correct 45 ms 2024 KB Output is correct
55 Correct 37 ms 2024 KB Output is correct
56 Correct 34 ms 2004 KB Output is correct
57 Correct 53 ms 12444 KB Output is correct
58 Correct 50 ms 12156 KB Output is correct
59 Correct 58 ms 11992 KB Output is correct
60 Correct 472 ms 16264 KB Output is correct
61 Correct 462 ms 16532 KB Output is correct
62 Correct 456 ms 16576 KB Output is correct
63 Correct 470 ms 14144 KB Output is correct
64 Correct 403 ms 14148 KB Output is correct
65 Correct 414 ms 14028 KB Output is correct
66 Correct 181 ms 15524 KB Output is correct
67 Correct 410 ms 16332 KB Output is correct
68 Correct 399 ms 16336 KB Output is correct
69 Correct 398 ms 16328 KB Output is correct
70 Correct 406 ms 16584 KB Output is correct
71 Correct 446 ms 16464 KB Output is correct
72 Correct 413 ms 16332 KB Output is correct
73 Correct 408 ms 16608 KB Output is correct
74 Correct 456 ms 16456 KB Output is correct
75 Correct 177 ms 36840 KB Output is correct
76 Correct 150 ms 37332 KB Output is correct
77 Correct 146 ms 36672 KB Output is correct
78 Correct 150 ms 36568 KB Output is correct
79 Correct 200 ms 36540 KB Output is correct
80 Correct 142 ms 37056 KB Output is correct
81 Correct 1748 ms 51004 KB Output is correct
82 Correct 1539 ms 50644 KB Output is correct
83 Correct 1557 ms 49584 KB Output is correct
84 Correct 1605 ms 51364 KB Output is correct
85 Correct 1541 ms 50864 KB Output is correct
86 Correct 1505 ms 49196 KB Output is correct
87 Correct 1816 ms 49720 KB Output is correct
88 Correct 1492 ms 42216 KB Output is correct
89 Correct 1506 ms 42736 KB Output is correct
90 Correct 1483 ms 43256 KB Output is correct
91 Correct 1485 ms 42496 KB Output is correct
92 Correct 1535 ms 42292 KB Output is correct
93 Correct 1295 ms 48592 KB Output is correct
94 Correct 1523 ms 49752 KB Output is correct
95 Correct 1327 ms 50192 KB Output is correct
96 Correct 1485 ms 49336 KB Output is correct
97 Correct 1868 ms 49868 KB Output is correct
98 Correct 781 ms 46008 KB Output is correct
99 Correct 1389 ms 50292 KB Output is correct
100 Correct 1222 ms 49076 KB Output is correct
101 Correct 1033 ms 47176 KB Output is correct
102 Correct 1291 ms 50132 KB Output is correct
103 Correct 1971 ms 49872 KB Output is correct
104 Correct 1369 ms 49004 KB Output is correct
105 Correct 800 ms 45896 KB Output is correct
106 Correct 1229 ms 50008 KB Output is correct
107 Correct 1225 ms 48984 KB Output is correct
108 Correct 1212 ms 49552 KB Output is correct
109 Correct 1231 ms 49672 KB Output is correct
110 Correct 1250 ms 48432 KB Output is correct
111 Correct 1271 ms 50028 KB Output is correct
112 Correct 1244 ms 49584 KB Output is correct
113 Correct 1282 ms 48520 KB Output is correct
114 Correct 1234 ms 50284 KB Output is correct
115 Correct 1240 ms 49028 KB Output is correct
116 Correct 1182 ms 48372 KB Output is correct