Submission #635908

#	Time	Username	Problem	Language	Result	Execution time	Memory
635908		MohamedFaresNebili	Park (BOI16_park)	C++14	100 / 100	1040 ms	33264 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42