oj.uz

Submission #450355

# Submission time Handle Problem Language Result Execution time Memory
450355 2021-08-02T15:32:39 Z ymm Circle selection (APIO18_circle_selection) C++17
7 / 100
 3000 ms 322220 KB 
///
///    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 << ' ';
}

Subtask #1
7.0 / 7.0

# 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

Subtask #2
0 / 12.0

# 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 -

Subtask #3
0 / 15.0

# 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 -

Subtask #4
0 / 23.0

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

Subtask #5
0 / 30.0

# 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 -

Subtask #6
0 / 13.0

# 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 -