oj.uz

Submission #777251

# Submission time Handle Problem Language Result Execution time Memory
777251 2023-07-08T21:08:23 Z Sam_a17 Circle selection (APIO18_circle_selection) C++17
100 / 100
 1869 ms 58752 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int)x.size()
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt __builtin_popcount
 
#define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// Indexed Set  
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
// template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(Tree <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
 
 
// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  // if(str == "input") {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
  // } else if(str != "") {
    // freopen((str + ".in").c_str(), "r", stdin);
    // freopen((str + ".out").c_str(), "w", stdout);
  // }
}
 
const long long inf = 1e9 + 1;
int n;
 
long long dist(pair<long long, long long> a, pair<long long, long long> b) {
  return abs(a.first - b.first) * abs(a.first - b.first) + abs(a.second - b.second) * abs(a.second - b.second);
}
 
struct node {
  long long x, y, r;
  int index;
};
 
map<pair<long long, long long>, vector<node>> mp;
 
bool cmp(node a, node b) {
  if(a.r > b.r) {
    return true;
  } else if(a.r < b.r) {
    return false;
  } else {
    if(a.index < b.index) {
      return true;
    } else {
      return false;
    }
  }
}
 
void solve_() {
  cin >> n;
 
  vector<node> a;
  long long cur_r, cur;
  for(int i = 1; i <= n; i++) {
    long long x, y, r; cin >> x >> y >> r;
    x += inf, y += inf;
    a.push_back({x, y, r, i});
  }
 
  sort(all(a), cmp);
 
  vector<int> which(n + 1);
  long long mx = -1;
  
  for(int w = 0; w < n; w++) {
    int ind = a[w].index;
    if(which[ind]) continue;
    if(mx == -1 || mx / 2 > a[w].r) {
      mx = a[w].r;
      mp.clear();
 
      vector<node> new_a;
      for(int i = 0; i < n; i++) {
        if(which[a[i].index]) {
          continue;
        }
        long long cx = a[i].x / mx;
        long long cy = a[i].y / mx;
        mp[{cx, cy}].push_back(a[i]);
      }
    }
 
    long long cur_x = a[w].x / mx;
    long long cur_y = a[w].y / mx;
 
    for(int i = cur_x - 2; i <= cur_x + 2; i++) {
      for(int j = cur_y - 2; j <= cur_y + 2; j++) {
        if(mp.find({i, j}) == mp.end()) continue;
 
        for(auto k: mp[{i, j}]) {
          if(which[k.index]) continue;
          
          if(dist({a[w].x, a[w].y}, {k.x, k.y}) <= (a[w].r + k.r) * (a[w].r + k.r)) {
            which[k.index] = ind;
          }
        }
      }
    }
 
  }
 
  for(int i = 1; i <= n; i++) {
    assert(which[i]);
    cout << which[i] << " ";
  }
  cout << '\n';
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    for(int i = 1; i <= test_case; i++) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

circle_selection.cpp: In function 'void solve_()':
circle_selection.cpp:116:13: warning: unused variable 'cur_r' [-Wunused-variable]
  116 |   long long cur_r, cur;
      |             ^~~~~
circle_selection.cpp:116:20: warning: unused variable 'cur' [-Wunused-variable]
  116 |   long long cur_r, cur;
      |                    ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 856 KB Output is correct
20 Correct 3 ms 728 KB Output is correct
21 Correct 2 ms 728 KB Output is correct
22 Correct 11 ms 1148 KB Output is correct
23 Correct 12 ms 1140 KB Output is correct
24 Correct 11 ms 1152 KB Output is correct
25 Correct 10 ms 1112 KB Output is correct
26 Correct 11 ms 1112 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 29424 KB Output is correct
2 Correct 140 ms 26616 KB Output is correct
3 Correct 137 ms 28020 KB Output is correct
4 Correct 147 ms 26872 KB Output is correct
5 Correct 180 ms 28380 KB Output is correct
6 Correct 567 ms 42524 KB Output is correct
7 Correct 230 ms 35600 KB Output is correct
8 Correct 284 ms 36520 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 334 ms 16868 KB Output is correct
3 Correct 1539 ms 58480 KB Output is correct
4 Correct 1634 ms 58536 KB Output is correct
5 Correct 1553 ms 52672 KB Output is correct
6 Correct 518 ms 27024 KB Output is correct
7 Correct 193 ms 14496 KB Output is correct
8 Correct 32 ms 3256 KB Output is correct
9 Correct 1851 ms 57736 KB Output is correct
10 Correct 1323 ms 53108 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1272 ms 50376 KB Output is correct
2 Correct 908 ms 50380 KB Output is correct
3 Correct 349 ms 33400 KB Output is correct
4 Correct 905 ms 50516 KB Output is correct
5 Correct 900 ms 50376 KB Output is correct
6 Correct 200 ms 30080 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 856 KB Output is correct
20 Correct 3 ms 728 KB Output is correct
21 Correct 2 ms 728 KB Output is correct
22 Correct 11 ms 1148 KB Output is correct
23 Correct 12 ms 1140 KB Output is correct
24 Correct 11 ms 1152 KB Output is correct
25 Correct 10 ms 1112 KB Output is correct
26 Correct 11 ms 1112 KB Output is correct
27 Correct 5 ms 1108 KB Output is correct
28 Correct 5 ms 1508 KB Output is correct
29 Correct 5 ms 1452 KB Output is correct
30 Correct 26 ms 2072 KB Output is correct
31 Correct 23 ms 2024 KB Output is correct
32 Correct 23 ms 1996 KB Output is correct
33 Correct 47 ms 11580 KB Output is correct
34 Correct 47 ms 9708 KB Output is correct
35 Correct 49 ms 8252 KB Output is correct
36 Correct 327 ms 17008 KB Output is correct
37 Correct 316 ms 19524 KB Output is correct
38 Correct 305 ms 19564 KB Output is correct
39 Correct 270 ms 16808 KB Output is correct
40 Correct 259 ms 16664 KB Output is correct
41 Correct 279 ms 16640 KB Output is correct
42 Correct 181 ms 18432 KB Output is correct
43 Correct 216 ms 19248 KB Output is correct
44 Correct 216 ms 19384 KB Output is correct
45 Correct 224 ms 19268 KB Output is correct
46 Correct 225 ms 19332 KB Output is correct
47 Correct 229 ms 19348 KB Output is correct
48 Correct 212 ms 19352 KB Output is correct
49 Correct 209 ms 19256 KB Output is correct
50 Correct 218 ms 19336 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 3 ms 856 KB Output is correct
20 Correct 3 ms 728 KB Output is correct
21 Correct 2 ms 728 KB Output is correct
22 Correct 11 ms 1148 KB Output is correct
23 Correct 12 ms 1140 KB Output is correct
24 Correct 11 ms 1152 KB Output is correct
25 Correct 10 ms 1112 KB Output is correct
26 Correct 11 ms 1112 KB Output is correct
27 Correct 134 ms 29424 KB Output is correct
28 Correct 140 ms 26616 KB Output is correct
29 Correct 137 ms 28020 KB Output is correct
30 Correct 147 ms 26872 KB Output is correct
31 Correct 180 ms 28380 KB Output is correct
32 Correct 567 ms 42524 KB Output is correct
33 Correct 230 ms 35600 KB Output is correct
34 Correct 284 ms 36520 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 334 ms 16868 KB Output is correct
37 Correct 1539 ms 58480 KB Output is correct
38 Correct 1634 ms 58536 KB Output is correct
39 Correct 1553 ms 52672 KB Output is correct
40 Correct 518 ms 27024 KB Output is correct
41 Correct 193 ms 14496 KB Output is correct
42 Correct 32 ms 3256 KB Output is correct
43 Correct 1851 ms 57736 KB Output is correct
44 Correct 1323 ms 53108 KB Output is correct
45 Correct 1272 ms 50376 KB Output is correct
46 Correct 908 ms 50380 KB Output is correct
47 Correct 349 ms 33400 KB Output is correct
48 Correct 905 ms 50516 KB Output is correct
49 Correct 900 ms 50376 KB Output is correct
50 Correct 200 ms 30080 KB Output is correct
51 Correct 5 ms 1108 KB Output is correct
52 Correct 5 ms 1508 KB Output is correct
53 Correct 5 ms 1452 KB Output is correct
54 Correct 26 ms 2072 KB Output is correct
55 Correct 23 ms 2024 KB Output is correct
56 Correct 23 ms 1996 KB Output is correct
57 Correct 47 ms 11580 KB Output is correct
58 Correct 47 ms 9708 KB Output is correct
59 Correct 49 ms 8252 KB Output is correct
60 Correct 327 ms 17008 KB Output is correct
61 Correct 316 ms 19524 KB Output is correct
62 Correct 305 ms 19564 KB Output is correct
63 Correct 270 ms 16808 KB Output is correct
64 Correct 259 ms 16664 KB Output is correct
65 Correct 279 ms 16640 KB Output is correct
66 Correct 181 ms 18432 KB Output is correct
67 Correct 216 ms 19248 KB Output is correct
68 Correct 216 ms 19384 KB Output is correct
69 Correct 224 ms 19268 KB Output is correct
70 Correct 225 ms 19332 KB Output is correct
71 Correct 229 ms 19348 KB Output is correct
72 Correct 212 ms 19352 KB Output is correct
73 Correct 209 ms 19256 KB Output is correct
74 Correct 218 ms 19336 KB Output is correct
75 Correct 163 ms 36364 KB Output is correct
76 Correct 152 ms 34560 KB Output is correct
77 Correct 148 ms 44368 KB Output is correct
78 Correct 145 ms 40500 KB Output is correct
79 Correct 201 ms 33944 KB Output is correct
80 Correct 143 ms 37456 KB Output is correct
81 Correct 1550 ms 58448 KB Output is correct
82 Correct 1451 ms 58312 KB Output is correct
83 Correct 1422 ms 58188 KB Output is correct
84 Correct 1654 ms 58752 KB Output is correct
85 Correct 1466 ms 58268 KB Output is correct
86 Correct 1433 ms 58396 KB Output is correct
87 Correct 1869 ms 58312 KB Output is correct
88 Correct 1211 ms 49664 KB Output is correct
89 Correct 1199 ms 49800 KB Output is correct
90 Correct 1285 ms 49656 KB Output is correct
91 Correct 1185 ms 49640 KB Output is correct
92 Correct 1212 ms 49656 KB Output is correct
93 Correct 1119 ms 57292 KB Output is correct
94 Correct 1239 ms 57632 KB Output is correct
95 Correct 1048 ms 57300 KB Output is correct
96 Correct 1174 ms 57312 KB Output is correct
97 Correct 1671 ms 57236 KB Output is correct
98 Correct 749 ms 47884 KB Output is correct
99 Correct 1149 ms 57472 KB Output is correct
100 Correct 960 ms 57308 KB Output is correct
101 Correct 1020 ms 52028 KB Output is correct
102 Correct 1152 ms 56960 KB Output is correct
103 Correct 1726 ms 57008 KB Output is correct
104 Correct 1136 ms 57168 KB Output is correct
105 Correct 819 ms 54968 KB Output is correct
106 Correct 841 ms 56316 KB Output is correct
107 Correct 830 ms 56512 KB Output is correct
108 Correct 787 ms 56364 KB Output is correct
109 Correct 836 ms 56416 KB Output is correct
110 Correct 850 ms 56356 KB Output is correct
111 Correct 812 ms 56352 KB Output is correct
112 Correct 838 ms 56448 KB Output is correct
113 Correct 823 ms 56388 KB Output is correct
114 Correct 811 ms 56424 KB Output is correct
115 Correct 814 ms 56408 KB Output is correct
116 Correct 797 ms 56412 KB Output is correct