oj.uz

Submission #970400

# Submission time Handle Problem Language Result Execution time Memory
970400 2024-04-26T13:31:32 Z steveonalex Circle selection (APIO18_circle_selection) C++17
52 / 100
 2309 ms 55176 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 3e5 + 69;
const ll INF = 1e9;
int n; 
int ans[N];
vector<array<ll, 4>> a;

ll sqr(ll x){return x * x;}
ll block_sz;
map<pair<ll, ll>, vector<int>> grid;

pair<ll, ll> dumb_down(pair<ll, ll> a){
    return {a.first / block_sz, a.second / block_sz};
}

void set_up(ll arg){
    block_sz = arg;

    grid.clear();
    for(int i= 1; i<=n; ++i) if (ans[i] == 0){
        grid[dumb_down(make_pair(a[i][0], a[i][1]))].push_back(i);
    }
}

ll dis(pair<ll, ll> a, pair<ll, ll> b){return sqr(a.first - b.first) + sqr(a.second - b.second);}

bool check(pair<ll, ll> point, ll r, pair<ll, ll> des){
    if (des.first < 0 || des.second < 0) return false;
    for(int x = 0; x <= 1; ++x) for(int y = 0; y<=1; ++y){
        pair<ll, ll> ligma = {des.first * block_sz, des.second * block_sz};
        if (x) ligma.first += block_sz - 1;
        if (y) ligma.second += block_sz - 1;
        if (abs(point.first - ligma.first) + abs(point.second - ligma.second) > r * 2) continue;
        if (dis(point, ligma) <= sqr(r)) return true;
    }
    return false;
}

bool query(int i, int j){
    return sqr(a[i][0] - a[j][0]) + sqr(a[i][1] - a[j][1]) <= sqr(a[i][2] + a[j][2]);
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n;
    a.resize(n+1);
    for(int i = 1; i<=n; ++i) {
        for(int j = 0; j < 3; ++j) cin >> a[i][j];
        a[i][0] += INF; a[i][1] += INF;
        a[i][3] = i;
    }

    vector<array<ll, 4>> b = a;
    sort(1 + ALL(b), [](array<ll, 4> x, array<ll, 4> y){
        if (x[2] != y[2]) return x[2] > y[2];
        return x[3] < y[3];
    });

    set_up((b[1][2] + 1) / 2);
    for(int i = 1; i<=n; ++i) if (ans[b[i][3]] == 0){
        int _i = b[i][3];
        ans[_i] = _i;

        if (b[i][2] < block_sz)
            set_up((b[i][2] + 1) / 2);

        pair<ll, ll> cur = make_pair(b[i][0], b[i][1]);
        pair<ll, ll> magnifico = dumb_down(cur);
        const int EXTEND = 5;
        for(int x = -EXTEND; x <= EXTEND; ++x) for(int y = -EXTEND; y<=EXTEND; ++y) {
            pair<ll, ll> cu = make_pair(magnifico.first + x, magnifico.second + y);

            bool bruh = check(cur, b[i][2] * 2, cu);

            if (!bruh || !grid.count(cu)) continue;
            for(int j: grid[cu]){
                if (ans[j] == 0 && query(_i, j)) ans[j] = _i;
            }
        }
    }

    for(int i = 1; i<=n; ++i) 
        cout << ans[i] << " "; 
    cout << "\n";

    return 0;
}

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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 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 348 KB Output is correct
19 Correct 2 ms 636 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 3 ms 860 KB Output is correct
22 Correct 21 ms 1368 KB Output is correct
23 Correct 22 ms 1372 KB Output is correct
24 Correct 19 ms 1372 KB Output is correct
25 Correct 18 ms 1372 KB Output is correct
26 Correct 19 ms 1372 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 22948 KB Output is correct
2 Correct 120 ms 22680 KB Output is correct
3 Correct 114 ms 23424 KB Output is correct
4 Correct 108 ms 22580 KB Output is correct
5 Incorrect 177 ms 25736 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 557 ms 18452 KB Output is correct
3 Correct 2045 ms 55120 KB Output is correct
4 Correct 2054 ms 55072 KB Output is correct
5 Correct 1853 ms 51448 KB Output is correct
6 Correct 623 ms 26884 KB Output is correct
7 Correct 240 ms 14420 KB Output is correct
8 Correct 40 ms 3412 KB Output is correct
9 Correct 2309 ms 55024 KB Output is correct
10 Correct 1644 ms 51368 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2126 ms 55068 KB Output is correct
2 Correct 1184 ms 55176 KB Output is correct
3 Incorrect 557 ms 44240 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 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 348 KB Output is correct
19 Correct 2 ms 636 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 3 ms 860 KB Output is correct
22 Correct 21 ms 1368 KB Output is correct
23 Correct 22 ms 1372 KB Output is correct
24 Correct 19 ms 1372 KB Output is correct
25 Correct 18 ms 1372 KB Output is correct
26 Correct 19 ms 1372 KB Output is correct
27 Correct 5 ms 1116 KB Output is correct
28 Correct 4 ms 1116 KB Output is correct
29 Correct 4 ms 1112 KB Output is correct
30 Correct 51 ms 2228 KB Output is correct
31 Correct 43 ms 2228 KB Output is correct
32 Correct 39 ms 2136 KB Output is correct
33 Correct 40 ms 8152 KB Output is correct
34 Correct 40 ms 8140 KB Output is correct
35 Correct 44 ms 7852 KB Output is correct
36 Correct 496 ms 18496 KB Output is correct
37 Correct 466 ms 18584 KB Output is correct
38 Correct 469 ms 18516 KB Output is correct
39 Correct 253 ms 17048 KB Output is correct
40 Correct 220 ms 17048 KB Output is correct
41 Correct 236 ms 17004 KB Output is correct
42 Correct 262 ms 18512 KB Output is correct
43 Correct 405 ms 18468 KB Output is correct
44 Correct 402 ms 18468 KB Output is correct
45 Correct 411 ms 18460 KB Output is correct
46 Correct 397 ms 18508 KB Output is correct
47 Correct 407 ms 18468 KB Output is correct
48 Correct 398 ms 18512 KB Output is correct
49 Correct 418 ms 18464 KB Output is correct
50 Correct 409 ms 18704 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 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 348 KB Output is correct
19 Correct 2 ms 636 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 3 ms 860 KB Output is correct
22 Correct 21 ms 1368 KB Output is correct
23 Correct 22 ms 1372 KB Output is correct
24 Correct 19 ms 1372 KB Output is correct
25 Correct 18 ms 1372 KB Output is correct
26 Correct 19 ms 1372 KB Output is correct
27 Correct 113 ms 22948 KB Output is correct
28 Correct 120 ms 22680 KB Output is correct
29 Correct 114 ms 23424 KB Output is correct
30 Correct 108 ms 22580 KB Output is correct
31 Incorrect 177 ms 25736 KB Output isn't correct
32 Halted 0 ms 0 KB -