///
/// I have a dream and a piano
///
#define _USE_MATH_DEFINES
#define FAST ios::sync_with_stdio(false),cin.tie(0);
#include <bits/stdc++.h>
#define Loop(x, l, r) for(int x = (l); x < (r); ++x)
#define LoopR(x, l, r) for(int x = (r)-1; x >= (l); --x)
#define all(x) x.begin(), x.end()
#define Kill(x) exit((cout << (x) << '\n', 0))
#define YN(flag) ((flag)? "YES": "NO")
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int,int> pii;
typedef std::pair<ll ,ll > pll;
using namespace std;
const int N = 300'010;
ll r[N], x[N], y[N];
inline ll sqr(ll x){return x*x;}
inline bool g(int i, int j){return sqr(x[i]-x[j]) + sqr(y[i]-y[j]) <= sqr(r[i]+r[j]);}
map<pll, vector<pii>> mp[32];
int ans[N];
pll circ[N];
int n;
int main()
{
FAST;
cin >> n;
Loop(i,0,n)
{
cin >> x[i] >> y[i] >> r[i];
x[i] += 1e9; y[i] += 1e9;
circ[i] = {~r[i], i};
}
sort(circ, circ+n);
Loop(_,0,n)
{
int i = circ[_].S;
int lg = r[i]==1?0:32-__builtin_clz(r[i]-1);
int mn = 1e9;
for(int k = lg; k < 32; ++k)
{
ll r = k? 1<<(k-1): 0;
ll d = r? 2*r: 1;
// (r, d]
Loop(xx,-1,2) Loop(yy,-1,2)
for(auto [j1, j2] : mp[k][pll{x[i]/(2*d)+xx, y[i]/(2*d)+yy}])
if(g(i,j2))
mn = min(j1, mn);
}
if(mn == 1e9){
ll r = lg? 1<<(lg-1): 0;
ll d = r? 2*r: 1;
mp[lg][pll{x[i]/(2*d), y[i]/(2*d)}].emplace_back(_, i);
ans[i] = i;
} else ans[i] = circ[mn].S;
}
Loop(i,0,n) cout << ans[i]+1 << ' ';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
972 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
13 |
Correct |
3 ms |
1100 KB |
Output is correct |
14 |
Correct |
3 ms |
972 KB |
Output is correct |
15 |
Correct |
2 ms |
716 KB |
Output is correct |
16 |
Correct |
2 ms |
460 KB |
Output is correct |
17 |
Correct |
3 ms |
460 KB |
Output is correct |
18 |
Correct |
2 ms |
464 KB |
Output is correct |
19 |
Correct |
6 ms |
716 KB |
Output is correct |
20 |
Correct |
5 ms |
716 KB |
Output is correct |
21 |
Correct |
6 ms |
844 KB |
Output is correct |
22 |
Correct |
154 ms |
24300 KB |
Output is correct |
23 |
Correct |
163 ms |
22888 KB |
Output is correct |
24 |
Correct |
170 ms |
24004 KB |
Output is correct |
25 |
Correct |
210 ms |
36052 KB |
Output is correct |
26 |
Correct |
178 ms |
27780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
362 ms |
22532 KB |
Output is correct |
2 |
Correct |
391 ms |
22720 KB |
Output is correct |
3 |
Correct |
413 ms |
22340 KB |
Output is correct |
4 |
Correct |
361 ms |
22660 KB |
Output is correct |
5 |
Execution timed out |
3073 ms |
29404 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Execution timed out |
3066 ms |
245524 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3091 ms |
322220 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
972 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
13 |
Correct |
3 ms |
1100 KB |
Output is correct |
14 |
Correct |
3 ms |
972 KB |
Output is correct |
15 |
Correct |
2 ms |
716 KB |
Output is correct |
16 |
Correct |
2 ms |
460 KB |
Output is correct |
17 |
Correct |
3 ms |
460 KB |
Output is correct |
18 |
Correct |
2 ms |
464 KB |
Output is correct |
19 |
Correct |
6 ms |
716 KB |
Output is correct |
20 |
Correct |
5 ms |
716 KB |
Output is correct |
21 |
Correct |
6 ms |
844 KB |
Output is correct |
22 |
Correct |
154 ms |
24300 KB |
Output is correct |
23 |
Correct |
163 ms |
22888 KB |
Output is correct |
24 |
Correct |
170 ms |
24004 KB |
Output is correct |
25 |
Correct |
210 ms |
36052 KB |
Output is correct |
26 |
Correct |
178 ms |
27780 KB |
Output is correct |
27 |
Correct |
14 ms |
1340 KB |
Output is correct |
28 |
Correct |
15 ms |
1276 KB |
Output is correct |
29 |
Correct |
13 ms |
1256 KB |
Output is correct |
30 |
Correct |
350 ms |
42680 KB |
Output is correct |
31 |
Correct |
323 ms |
41220 KB |
Output is correct |
32 |
Correct |
410 ms |
50552 KB |
Output is correct |
33 |
Correct |
116 ms |
8768 KB |
Output is correct |
34 |
Correct |
109 ms |
9012 KB |
Output is correct |
35 |
Correct |
149 ms |
9540 KB |
Output is correct |
36 |
Execution timed out |
3083 ms |
294436 KB |
Time limit exceeded |
37 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
3 ms |
972 KB |
Output is correct |
12 |
Correct |
3 ms |
844 KB |
Output is correct |
13 |
Correct |
3 ms |
1100 KB |
Output is correct |
14 |
Correct |
3 ms |
972 KB |
Output is correct |
15 |
Correct |
2 ms |
716 KB |
Output is correct |
16 |
Correct |
2 ms |
460 KB |
Output is correct |
17 |
Correct |
3 ms |
460 KB |
Output is correct |
18 |
Correct |
2 ms |
464 KB |
Output is correct |
19 |
Correct |
6 ms |
716 KB |
Output is correct |
20 |
Correct |
5 ms |
716 KB |
Output is correct |
21 |
Correct |
6 ms |
844 KB |
Output is correct |
22 |
Correct |
154 ms |
24300 KB |
Output is correct |
23 |
Correct |
163 ms |
22888 KB |
Output is correct |
24 |
Correct |
170 ms |
24004 KB |
Output is correct |
25 |
Correct |
210 ms |
36052 KB |
Output is correct |
26 |
Correct |
178 ms |
27780 KB |
Output is correct |
27 |
Correct |
362 ms |
22532 KB |
Output is correct |
28 |
Correct |
391 ms |
22720 KB |
Output is correct |
29 |
Correct |
413 ms |
22340 KB |
Output is correct |
30 |
Correct |
361 ms |
22660 KB |
Output is correct |
31 |
Execution timed out |
3073 ms |
29404 KB |
Time limit exceeded |
32 |
Halted |
0 ms |
0 KB |
- |