oj.uz

Submission #581665

# Submission time Handle Problem Language Result Execution time Memory
581665 2022-06-23T02:31:07 Z DylanSmith Mecho (IOI09_mecho) Java 11
31 / 100
 641 ms 30920 KB 
import java.util.*;
import java.io.*;
public class mecho {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt(), K = in.nextInt();
        char[][] mat = new char[N][N];
        for (int i = 0; i < N; i++) {
            mat[i] = in.next().toCharArray();
        }
        Queue<int[]> q = new LinkedList<>();
        int[][] bee = new int[N][N];
        int[] start = new int[2], end = new int[2];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (mat[i][j] == 'H') {
                    bee[i][j] = 0;
                    q.offer(new int[]{i, j});
                } else {
                    bee[i][j] = -1;
                }
                if (mat[i][j] == 'M') {
                    start = new int[]{i, j};
                }
                if (mat[i][j] == 'D') {
                    end = new int[]{i, j};
                }
            }
        }
        int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
        while (!q.isEmpty()) {
            int[] current = q.poll();
            int r = current[0], c = current[1];
            for (int k = 0; k < 4; k++) {
                int r2 = r + x[k], c2 = c + y[k];
                if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < N) {
                    if (mat[r2][c2] != 'D' && bee[r2][c2] == -1) {
                        bee[r2][c2] = bee[r][c] + 1;
                        q.offer(new int[]{r2, c2});
                    }
                }
            }
        }
        out.println(search(mat, bee, start, end, K, 0, N * N));
        
        out.close();
    }
    public static int search(char[][] mat, int[][] bee, int[] start, int[] end, int K, int l, int r) {
        if (l > r) {
            return -1;
        }
        int mid = (l + r) / 2;
        if (check(mat, bee, start, end, K, mid)) {
            int m = search(mat, bee, start, end, K, mid + 1, r);
            if (m == -1) {
                return mid;
            }
            return m;
        }
        return search(mat, bee, start, end, K, l, mid - 1);
    }
    public static boolean check(char[][] mat, int[][] bee, int[] start, int[] end, int K, int eat) {
        int N = mat.length;
        int[][] dist = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dist[i], -1);
        }
        dist[start[0]][start[1]] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(start);
        int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
        while (!q.isEmpty()) {
            int[] current = q.poll();
            int r = current[0], c = current[1];
            for (int k = 0; k < 4; k++) {
                int r2 = r + x[k], c2 = c + y[k];
                if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < N) {
                    if (mat[r2][c2] != 'T' && mat[r2][c2] != 'H' && dist[r2][c2] == -1) {
                        if (mat[r2][c2] == 'D' || (dist[r][c] + 1) / K + eat < bee[r2][c2]) {
                            dist[r2][c2] = dist[r][c] + 1;
                            q.offer(new int[]{r2, c2});
                        }
                    }
                }
            }
        }
        return dist[end[0]][end[1]] >= 0;
    }
    static class Reader {
        BufferedInputStream in;
        public Reader() {
            in = new BufferedInputStream(System.in);
        }
        public String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public String next() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != ' ' && c != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public int nextInt() throws IOException {
            return (int)nextLong();
        }
        public long nextLong() throws IOException {
            int c;
            long res = 0;
            boolean start = false, negative = false;
            while ((c = in.read()) != ' ' && c != '\n' || !start)
                if (c >= '0' && c <= '9' || c == '-') {
                    start = true;
                    if (c == '-')
                        negative = true;
                    else
                        res = res * 10 + c - '0';
                }
            return res * (negative ? -1 : 1);
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

Subtask #1
31.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8344 KB Output is correct
2 Correct 62 ms 8448 KB Output is correct
3 Correct 59 ms 8456 KB Output is correct
4 Incorrect 63 ms 8340 KB Output isn't correct
5 Incorrect 64 ms 8124 KB Output isn't correct
6 Correct 70 ms 8356 KB Output is correct
7 Correct 504 ms 29272 KB Output is correct
8 Correct 77 ms 8276 KB Output is correct
9 Incorrect 64 ms 8532 KB Output isn't correct
10 Correct 64 ms 8324 KB Output is correct
11 Correct 63 ms 8380 KB Output is correct
12 Incorrect 86 ms 10008 KB Output isn't correct
13 Incorrect 82 ms 8664 KB Output isn't correct
14 Correct 165 ms 11780 KB Output is correct
15 Incorrect 61 ms 8552 KB Output isn't correct
16 Incorrect 57 ms 8500 KB Output isn't correct
17 Incorrect 62 ms 8104 KB Output isn't correct
18 Incorrect 70 ms 8188 KB Output isn't correct
19 Incorrect 77 ms 8400 KB Output isn't correct
20 Incorrect 68 ms 8316 KB Output isn't correct
21 Incorrect 66 ms 8572 KB Output isn't correct
22 Incorrect 71 ms 8500 KB Output isn't correct
23 Incorrect 72 ms 8644 KB Output isn't correct
24 Incorrect 76 ms 8532 KB Output isn't correct
25 Incorrect 86 ms 10000 KB Output isn't correct
26 Incorrect 83 ms 10124 KB Output isn't correct
27 Incorrect 91 ms 9988 KB Output isn't correct
28 Incorrect 121 ms 10268 KB Output isn't correct
29 Incorrect 88 ms 10244 KB Output isn't correct
30 Incorrect 102 ms 10568 KB Output isn't correct
31 Incorrect 101 ms 10444 KB Output isn't correct
32 Incorrect 120 ms 10340 KB Output isn't correct
33 Incorrect 201 ms 14360 KB Output isn't correct
34 Incorrect 221 ms 14828 KB Output isn't correct
35 Correct 390 ms 18580 KB Output is correct
36 Incorrect 209 ms 15412 KB Output isn't correct
37 Incorrect 247 ms 15364 KB Output isn't correct
38 Correct 363 ms 19160 KB Output is correct
39 Incorrect 190 ms 16288 KB Output isn't correct
40 Incorrect 249 ms 16248 KB Output isn't correct
41 Correct 396 ms 19208 KB Output is correct
42 Incorrect 243 ms 17100 KB Output isn't correct
43 Incorrect 217 ms 17504 KB Output isn't correct
44 Correct 416 ms 19464 KB Output is correct
45 Incorrect 242 ms 18740 KB Output isn't correct
46 Incorrect 250 ms 19248 KB Output isn't correct
47 Correct 426 ms 20484 KB Output is correct
48 Incorrect 261 ms 21072 KB Output isn't correct
49 Incorrect 248 ms 21148 KB Output isn't correct
50 Correct 434 ms 22120 KB Output is correct
51 Incorrect 242 ms 19548 KB Output isn't correct
52 Incorrect 258 ms 20516 KB Output isn't correct
53 Correct 527 ms 23116 KB Output is correct
54 Incorrect 255 ms 23104 KB Output isn't correct
55 Incorrect 271 ms 23600 KB Output isn't correct
56 Correct 559 ms 24468 KB Output is correct
57 Incorrect 264 ms 26324 KB Output isn't correct
58 Incorrect 287 ms 26044 KB Output isn't correct
59 Correct 582 ms 26372 KB Output is correct
60 Incorrect 286 ms 25524 KB Output isn't correct
61 Incorrect 291 ms 26720 KB Output isn't correct
62 Correct 599 ms 28384 KB Output is correct
63 Incorrect 290 ms 26216 KB Output isn't correct
64 Incorrect 641 ms 28388 KB Output isn't correct
65 Incorrect 540 ms 28424 KB Output isn't correct
66 Incorrect 311 ms 26324 KB Output isn't correct
67 Correct 332 ms 29368 KB Output is correct
68 Incorrect 315 ms 27872 KB Output isn't correct
69 Incorrect 447 ms 27956 KB Output isn't correct
70 Incorrect 342 ms 27968 KB Output isn't correct
71 Incorrect 326 ms 27908 KB Output isn't correct
72 Incorrect 369 ms 27888 KB Output isn't correct
73 Incorrect 365 ms 27388 KB Output isn't correct
74 Correct 485 ms 28928 KB Output is correct
75 Correct 510 ms 28912 KB Output is correct
76 Correct 474 ms 28564 KB Output is correct
77 Correct 461 ms 28880 KB Output is correct
78 Correct 421 ms 28484 KB Output is correct
79 Correct 427 ms 28488 KB Output is correct
80 Correct 508 ms 28468 KB Output is correct
81 Correct 481 ms 28496 KB Output is correct
82 Correct 473 ms 28556 KB Output is correct
83 Correct 434 ms 28492 KB Output is correct
84 Correct 506 ms 28468 KB Output is correct
85 Correct 505 ms 28308 KB Output is correct
86 Correct 482 ms 28628 KB Output is correct
87 Correct 495 ms 28612 KB Output is correct
88 Correct 435 ms 30512 KB Output is correct
89 Correct 548 ms 30652 KB Output is correct
90 Correct 512 ms 30768 KB Output is correct
91 Correct 499 ms 30796 KB Output is correct
92 Correct 532 ms 30920 KB Output is correct