oj.uz

Submission #635908

# Submission time Handle Problem Language Result Execution time Memory
635908 2022-08-27T11:06:14 Z MohamedFaresNebili Park (BOI16_park) C++14
100 / 100
 1040 ms 33264 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define int ll
            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            int N, M, W, H;
            int X[2005], Y[20005], R[20005];
            int D[2005][2005], res[4][4];
            int solve(int state) {
                int ans = LONG_LONG_MAX;
                vector<int> dist(N + 1, LONG_LONG_MAX);
                for(int l = 0; l < N; l++) {
                    dist[l] = min(X[l] - R[l], H - Y[l] - R[l]);
                    if(state == 0) dist[l] = min(dist[l], W - X[l] - R[l]);
                }
                vector<bool> vis(N + 1, 0);
                for(int _ = 0; _ < N; _++) {
                    int cur = -1;
                    for(int l = 0; l < N; l++) {
                        if(!vis[l] && (cur == -1 || dist[l] < dist[cur]))
                            cur = l;
                    }
                    vis[cur] = 1;
                    for(int l = 0; l < N; l++) {
                        if(vis[l]) continue;
                        dist[l] = min(dist[l], max(dist[cur], D[l][cur]));
                    }
                    ans = min(ans, max(dist[cur], Y[cur] - R[cur]));
                    if(state == 1) ans = min(ans, max(W - X[cur] - R[cur], dist[cur]));
                }
                return ans;
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M >> W >> H;
                for(int l = 0; l < N; l++)
                    cin >> X[l] >> Y[l] >> R[l];
                for(int l = 0; l < N; l++) {
                    for(int i = l + 1; i < N; i++) {
                        int lo = 1, hi = 1e9;
                        while(lo <= hi) {
                            int md = (lo + hi) / 2;
                            int dx = (X[l] - X[i]) * (X[l] - X[i]);
                            int dy = (Y[l] - Y[i]) * (Y[l] - Y[i]);
                            int xr = (md + R[l] + R[i]) * (md + R[l] + R[i]);
                            if(xr <= dx + dy) D[l][i] = md, lo = md + 1;
                            else hi = md - 1;
                        }
                        D[i][l] = D[l][i];
                    }
                }
                for(int l = 0, i = 0, j = 1; l < 4; l++, i ^= 2) {
                    res[l][l] = LONG_LONG_MAX;
                    res[i][(i ^ j)] = res[(i ^ j)][i] = solve(0);
                    for(int e = 0; e < N; e++) Y[e] = H - Y[e];
                    if(l == 0) res[1][3] = res[3][1] = solve(1);
                    if(l == 1) {
                        res[0][2] = res[2][0] = solve(1);
						swap(H, W); j ^= 2;
                        for(int e = 0; e < N; e++)
                            swap(X[e], Y[e]);
                    }
                }
                for(int l = 0; l < M; l++) {
                    int A, B; cin >> A >> B; B--;
                    for(int i = 0; i < 4; i++)
                        if(res[B][i] >= 2 * A) cout << i + 1;
                    cout << "\n";
                }
                return 0;
            }

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 31912 KB Output is correct
2 Correct 1004 ms 31812 KB Output is correct
3 Correct 994 ms 31824 KB Output is correct
4 Correct 1040 ms 31816 KB Output is correct
5 Correct 1037 ms 31816 KB Output is correct
6 Correct 990 ms 31912 KB Output is correct
7 Correct 763 ms 31916 KB Output is correct
8 Correct 733 ms 31812 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 2840 KB Output is correct
2 Correct 35 ms 2836 KB Output is correct
3 Correct 34 ms 2708 KB Output is correct
4 Correct 34 ms 2756 KB Output is correct
5 Correct 35 ms 2776 KB Output is correct
6 Correct 36 ms 2876 KB Output is correct
7 Correct 37 ms 1748 KB Output is correct
8 Correct 26 ms 1844 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 31912 KB Output is correct
2 Correct 1004 ms 31812 KB Output is correct
3 Correct 994 ms 31824 KB Output is correct
4 Correct 1040 ms 31816 KB Output is correct
5 Correct 1037 ms 31816 KB Output is correct
6 Correct 990 ms 31912 KB Output is correct
7 Correct 763 ms 31916 KB Output is correct
8 Correct 733 ms 31812 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 47 ms 2840 KB Output is correct
12 Correct 35 ms 2836 KB Output is correct
13 Correct 34 ms 2708 KB Output is correct
14 Correct 34 ms 2756 KB Output is correct
15 Correct 35 ms 2776 KB Output is correct
16 Correct 36 ms 2876 KB Output is correct
17 Correct 37 ms 1748 KB Output is correct
18 Correct 26 ms 1844 KB Output is correct
19 Correct 1033 ms 33168 KB Output is correct
20 Correct 1025 ms 33068 KB Output is correct
21 Correct 1016 ms 33152 KB Output is correct
22 Correct 1022 ms 33024 KB Output is correct
23 Correct 1025 ms 33020 KB Output is correct
24 Correct 768 ms 33264 KB Output is correct