답안 #571319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
571319	2022-06-01T18:24:59 Z	Vanilla	Mecho (IOI09_mecho)	C++17	21 / 100	345 ms	3836 KB

mecho

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 801;
char a [maxn][maxn];
char c [maxn][maxn];
bool vis [maxn][maxn];
bool bad [maxn][maxn];
int n,s, sx, sy, ex, ey;
queue <pair <int, int> > startq;
int dx[] = {-1, 0, 1, -1};
int dy[] = {0, 1, 0, -1};

bool check (int minutes) {
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            vis[i][j] = 0;
            bad[i][j] = 0;
            c[i][j] = a[i][j];
        }
    }
    queue <pair <int, int> > bear, bee = startq;
    bear.push({sx, sy}); 
    // move bees for minutes before starting search
    while (minutes--) {
        int k = bee.size();
        for (int i = 0; i < k; i++){
            int x = bee.front().first, y = bee.front().second;
            bad[x][y] = 1;
            bee.pop();
            for (int j = 0; j < 4; j++){
                int nx = x + dx[j], ny = y + dy[j];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || bad[nx][ny] || 
                    c[nx][ny] == 'T' || c[nx][ny] == 'D' || c[nx][ny] == 'H') continue;
                c[nx][ny] = 'H';
                bad[nx][ny] = 1;
                bee.push({nx, ny});
            }
        }
    }
    while (!bear.empty()){
        for (int z = 0; z < s; z++){
            int k = bear.size();
            for (int i = 0; i < k; i++){
                int x = bear.front().first, y = bear.front().second;
                bear.pop();
                if (bad[x][y]) continue;
                for (int j = 0; j < 4; j++){
                    int nx = x + dx[j], ny = y + dy[j];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n || vis[nx][ny] || 
                        c[nx][ny] == 'T' || c[nx][ny] == 'H') continue;
                    if (c[nx][ny] == 'D') return 1;
                    vis[nx][ny] = 1;
                    bear.push({nx, ny});
                }
            }
        }
        int k = bee.size();
        for (int i = 0; i < k; i++){
            int x = bee.front().first, y = bee.front().second;
            bad[x][y] = 1;
            bee.pop();
            for (int j = 0; j < 4; j++){
                int nx = x + dx[j], ny = y + dy[j];
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || bad[nx][ny] || 
                    c[nx][ny] == 'T' || c[nx][ny] == 'D' || c[nx][ny] == 'H') continue;
                c[nx][ny] = 'H';
                bad[nx][ny] = 1;
                bee.push({nx, ny});
            }
        }
    }
    return 0;

}

int main() {
    cin >> n >> s;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        for (int j = 0; j < n; j++){
            if (a[i][j] == 'M') {
                sx = i, sy = j;
            }
            if (a[i][j] == 'D') {
                ex = i, ey = j;
            }
            if (a[i][j] == 'H') {
                startq.push({i,j});
            }
        }
    }
    // check(0);
    int l = 0, r = maxn * maxn, rs = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            rs = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    cout << rs;
    return 0;
}

Subtask #1

21.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	212 KB	Output is correct
2	Incorrect	2 ms	340 KB	Output isn't correct
3	Correct	2 ms	340 KB	Output is correct
4	Incorrect	2 ms	340 KB	Output isn't correct
5	Correct	2 ms	312 KB	Output is correct
6	Incorrect	2 ms	308 KB	Output isn't correct
7	Incorrect	305 ms	3540 KB	Output isn't correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	2 ms	340 KB	Output is correct
10	Correct	2 ms	340 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Incorrect	30 ms	468 KB	Output isn't correct
13	Correct	5 ms	468 KB	Output is correct
14	Correct	5 ms	468 KB	Output is correct
15	Incorrect	2 ms	340 KB	Output isn't correct
16	Incorrect	31 ms	460 KB	Output isn't correct
17	Incorrect	3 ms	308 KB	Output isn't correct
18	Incorrect	29 ms	340 KB	Output isn't correct
19	Incorrect	2 ms	340 KB	Output isn't correct
20	Incorrect	31 ms	340 KB	Output isn't correct
21	Incorrect	2 ms	432 KB	Output isn't correct
22	Incorrect	34 ms	460 KB	Output isn't correct
23	Incorrect	2 ms	468 KB	Output isn't correct
24	Incorrect	32 ms	468 KB	Output isn't correct
25	Incorrect	2 ms	432 KB	Output isn't correct
26	Incorrect	31 ms	484 KB	Output isn't correct
27	Incorrect	3 ms	468 KB	Output isn't correct
28	Incorrect	30 ms	468 KB	Output isn't correct
29	Incorrect	2 ms	468 KB	Output isn't correct
30	Incorrect	31 ms	468 KB	Output isn't correct
31	Incorrect	3 ms	468 KB	Output isn't correct
32	Incorrect	29 ms	468 KB	Output isn't correct
33	Incorrect	7 ms	1492 KB	Output isn't correct
34	Incorrect	34 ms	1492 KB	Output isn't correct
35	Correct	41 ms	1492 KB	Output is correct
36	Incorrect	7 ms	1620 KB	Output isn't correct
37	Incorrect	38 ms	1620 KB	Output isn't correct
38	Correct	49 ms	1724 KB	Output is correct
39	Incorrect	7 ms	1852 KB	Output isn't correct
40	Incorrect	36 ms	1876 KB	Output isn't correct
41	Correct	62 ms	1852 KB	Output is correct
42	Incorrect	9 ms	2132 KB	Output isn't correct
43	Incorrect	42 ms	2132 KB	Output isn't correct
44	Correct	80 ms	2132 KB	Output is correct
45	Incorrect	11 ms	2296 KB	Output isn't correct
46	Incorrect	39 ms	2308 KB	Output isn't correct
47	Correct	90 ms	2320 KB	Output is correct
48	Incorrect	12 ms	2472 KB	Output isn't correct
49	Incorrect	39 ms	2488 KB	Output isn't correct
50	Correct	123 ms	2540 KB	Output is correct
51	Incorrect	13 ms	2752 KB	Output isn't correct
52	Incorrect	44 ms	2644 KB	Output isn't correct
53	Correct	136 ms	2772 KB	Output is correct
54	Incorrect	19 ms	2972 KB	Output isn't correct
55	Incorrect	41 ms	2860 KB	Output isn't correct
56	Correct	147 ms	2976 KB	Output is correct
57	Incorrect	15 ms	3156 KB	Output isn't correct
58	Incorrect	46 ms	3100 KB	Output isn't correct
59	Correct	206 ms	3212 KB	Output is correct
60	Incorrect	18 ms	3412 KB	Output isn't correct
61	Incorrect	48 ms	3308 KB	Output isn't correct
62	Correct	196 ms	3428 KB	Output is correct
63	Incorrect	288 ms	3532 KB	Output isn't correct
64	Incorrect	56 ms	3356 KB	Output isn't correct
65	Incorrect	57 ms	3412 KB	Output isn't correct
66	Incorrect	74 ms	3432 KB	Output isn't correct
67	Incorrect	56 ms	3432 KB	Output isn't correct
68	Incorrect	287 ms	3396 KB	Output isn't correct
69	Incorrect	278 ms	3420 KB	Output isn't correct
70	Incorrect	328 ms	3404 KB	Output isn't correct
71	Incorrect	304 ms	3468 KB	Output isn't correct
72	Incorrect	299 ms	3468 KB	Output isn't correct
73	Incorrect	327 ms	3720 KB	Output isn't correct
74	Incorrect	339 ms	3732 KB	Output isn't correct
75	Incorrect	345 ms	3720 KB	Output isn't correct
76	Incorrect	331 ms	3788 KB	Output isn't correct
77	Incorrect	322 ms	3836 KB	Output isn't correct
78	Correct	323 ms	3720 KB	Output is correct
79	Correct	306 ms	3696 KB	Output is correct
80	Correct	316 ms	3696 KB	Output is correct
81	Correct	312 ms	3692 KB	Output is correct
82	Correct	344 ms	3692 KB	Output is correct
83	Incorrect	225 ms	3644 KB	Output isn't correct
84	Incorrect	255 ms	3648 KB	Output isn't correct
85	Incorrect	235 ms	3672 KB	Output isn't correct
86	Incorrect	233 ms	3772 KB	Output isn't correct
87	Incorrect	231 ms	3648 KB	Output isn't correct
88	Incorrect	234 ms	3596 KB	Output isn't correct
89	Incorrect	225 ms	3660 KB	Output isn't correct
90	Incorrect	257 ms	3592 KB	Output isn't correct
91	Incorrect	249 ms	3572 KB	Output isn't correct
92	Incorrect	228 ms	3600 KB	Output isn't correct