Submission #794958

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
794958	2023-07-27T04:35:47 Z	sushikid	Mecho (IOI09_mecho)	Java 11	0 / 100	59 ms	8520 KB

mecho

import java.util.*;
import java.io.*;

public class mecho {
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

    private static int n, s;
    private static char[][] grid;
    private static int[][] bees;
    private static int[] start, end;

    private static boolean valid(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
    private static boolean check(int x){
        if(bees[start[0]][start[1]] <= x){
            return false;
        }

        boolean[][] dist = new boolean[n][n];
        Queue<int[]> cur = new LinkedList<>();
        cur.add(new int[]{start[0], start[1], 0});

        dist[start[0]][start[1]] = true;
        while(!cur.isEmpty()){
            int[] z = cur.poll();
            for (int i = 0; i < 4; i++) {
                int fx = z[0] + dx[i];
                int fy = z[1] + dy[i];
                if(valid(fx, fy) && !dist[fx][fy] && grid[fx][fy] != 'T' && (z[2] + 1)/s + x < bees[fx][fy]){
                    dist[fx][fy] = true;
                    cur.add(new int[]{fx, fy, z[2] + 1});
                }
            }
        }
        return dist[end[0]][end[1]];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new FileReader("test.in"));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(r.readLine());
        n = Integer.parseInt(st.nextToken()); s = Integer.parseInt(st.nextToken());

        grid = new char[n][n];
        start = new int[]{-1, -1}; end = new int[]{-1, -1};
        Queue<int[]> hives = new LinkedList<>();
        bees = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(bees[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < n; i++) {
            String str = r.readLine();
            for (int j = 0; j < n; j++) {
                if(str.charAt(j) == 'M'){
                    start = new int[]{i, j};
                }
                if(str.charAt(j) == 'D'){
                    end = new int[]{i, j};
                }
                if(str.charAt(j) == 'H'){
                    hives.add(new int[]{i, j, 0});
                    bees[i][j] = 0;
                }
                grid[i][j] = str.charAt(j);
            }
        }
        while(!hives.isEmpty()){
            int[] x = hives.poll();
            for (int i = 0; i < 4; i++) {
                int fx = x[0] + dx[i];
                int fy = x[1] + dy[i];
                if(valid(fx, fy) && bees[fx][fy] == Integer.MAX_VALUE && (grid[fx][fy] == 'G' || grid[fx][fy] == 'M')){
                    bees[fx][fy] = x[2] + 1;
                    hives.add(new int[]{fx, fy, x[2] + 1});
                }
            }
        }
        int left = 0;
        int right = 2 * n;
        while(left < right){
            int mid = left + (right - left + 1)/2;
            if(check(mid)){
                left = mid;
            }
            else{
                right = mid - 1;
            }
        }
        if(check(right)){
            pw.println(right);
        }
        else{
            pw.println(-1);
        }
        pw.close();
    }
}

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	59 ms	8096 KB	Execution failed because the return code was nonzero
2	Runtime error	48 ms	8212 KB	Execution failed because the return code was nonzero
3	Runtime error	51 ms	8296 KB	Execution failed because the return code was nonzero
4	Runtime error	48 ms	8520 KB	Execution failed because the return code was nonzero
5	Runtime error	49 ms	8332 KB	Execution failed because the return code was nonzero
6	Runtime error	50 ms	8360 KB	Execution failed because the return code was nonzero
7	Runtime error	49 ms	8228 KB	Execution failed because the return code was nonzero
8	Runtime error	56 ms	8244 KB	Execution failed because the return code was nonzero
9	Runtime error	49 ms	8148 KB	Execution failed because the return code was nonzero
10	Runtime error	47 ms	8260 KB	Execution failed because the return code was nonzero
11	Runtime error	49 ms	8348 KB	Execution failed because the return code was nonzero
12	Runtime error	51 ms	8120 KB	Execution failed because the return code was nonzero
13	Runtime error	47 ms	8264 KB	Execution failed because the return code was nonzero
14	Runtime error	48 ms	8044 KB	Execution failed because the return code was nonzero
15	Runtime error	48 ms	8284 KB	Execution failed because the return code was nonzero
16	Runtime error	49 ms	8164 KB	Execution failed because the return code was nonzero
17	Runtime error	50 ms	8424 KB	Execution failed because the return code was nonzero
18	Runtime error	49 ms	8136 KB	Execution failed because the return code was nonzero
19	Runtime error	48 ms	8220 KB	Execution failed because the return code was nonzero
20	Runtime error	51 ms	8188 KB	Execution failed because the return code was nonzero
21	Runtime error	54 ms	8152 KB	Execution failed because the return code was nonzero
22	Runtime error	49 ms	8204 KB	Execution failed because the return code was nonzero
23	Runtime error	49 ms	8316 KB	Execution failed because the return code was nonzero
24	Runtime error	53 ms	8168 KB	Execution failed because the return code was nonzero
25	Runtime error	47 ms	8408 KB	Execution failed because the return code was nonzero
26	Runtime error	50 ms	8092 KB	Execution failed because the return code was nonzero
27	Runtime error	56 ms	8336 KB	Execution failed because the return code was nonzero
28	Runtime error	48 ms	8132 KB	Execution failed because the return code was nonzero
29	Runtime error	48 ms	8212 KB	Execution failed because the return code was nonzero
30	Runtime error	47 ms	8420 KB	Execution failed because the return code was nonzero
31	Runtime error	47 ms	8276 KB	Execution failed because the return code was nonzero
32	Runtime error	51 ms	8236 KB	Execution failed because the return code was nonzero
33	Runtime error	49 ms	8180 KB	Execution failed because the return code was nonzero
34	Runtime error	52 ms	8380 KB	Execution failed because the return code was nonzero
35	Runtime error	49 ms	8276 KB	Execution failed because the return code was nonzero
36	Runtime error	58 ms	8296 KB	Execution failed because the return code was nonzero
37	Runtime error	47 ms	8152 KB	Execution failed because the return code was nonzero
38	Runtime error	49 ms	8188 KB	Execution failed because the return code was nonzero
39	Runtime error	48 ms	8096 KB	Execution failed because the return code was nonzero
40	Runtime error	48 ms	8348 KB	Execution failed because the return code was nonzero
41	Runtime error	48 ms	8428 KB	Execution failed because the return code was nonzero
42	Runtime error	57 ms	8264 KB	Execution failed because the return code was nonzero
43	Runtime error	47 ms	8152 KB	Execution failed because the return code was nonzero
44	Runtime error	48 ms	8300 KB	Execution failed because the return code was nonzero
45	Runtime error	48 ms	8308 KB	Execution failed because the return code was nonzero
46	Runtime error	50 ms	8196 KB	Execution failed because the return code was nonzero
47	Runtime error	56 ms	8172 KB	Execution failed because the return code was nonzero
48	Runtime error	47 ms	8040 KB	Execution failed because the return code was nonzero
49	Runtime error	48 ms	8480 KB	Execution failed because the return code was nonzero
50	Runtime error	51 ms	8248 KB	Execution failed because the return code was nonzero
51	Runtime error	51 ms	8364 KB	Execution failed because the return code was nonzero
52	Runtime error	48 ms	8468 KB	Execution failed because the return code was nonzero
53	Runtime error	50 ms	8068 KB	Execution failed because the return code was nonzero
54	Runtime error	50 ms	8088 KB	Execution failed because the return code was nonzero
55	Runtime error	48 ms	8388 KB	Execution failed because the return code was nonzero
56	Runtime error	48 ms	8296 KB	Execution failed because the return code was nonzero
57	Runtime error	49 ms	8288 KB	Execution failed because the return code was nonzero
58	Runtime error	47 ms	8332 KB	Execution failed because the return code was nonzero
59	Runtime error	47 ms	8496 KB	Execution failed because the return code was nonzero
60	Runtime error	48 ms	8212 KB	Execution failed because the return code was nonzero
61	Runtime error	50 ms	8372 KB	Execution failed because the return code was nonzero
62	Runtime error	50 ms	8288 KB	Execution failed because the return code was nonzero
63	Runtime error	57 ms	8260 KB	Execution failed because the return code was nonzero
64	Runtime error	49 ms	8068 KB	Execution failed because the return code was nonzero
65	Runtime error	48 ms	8404 KB	Execution failed because the return code was nonzero
66	Runtime error	53 ms	8104 KB	Execution failed because the return code was nonzero
67	Runtime error	48 ms	8224 KB	Execution failed because the return code was nonzero
68	Runtime error	48 ms	8384 KB	Execution failed because the return code was nonzero
69	Runtime error	48 ms	8396 KB	Execution failed because the return code was nonzero
70	Runtime error	52 ms	8200 KB	Execution failed because the return code was nonzero
71	Runtime error	49 ms	8184 KB	Execution failed because the return code was nonzero
72	Runtime error	48 ms	8360 KB	Execution failed because the return code was nonzero
73	Runtime error	47 ms	8228 KB	Execution failed because the return code was nonzero
74	Runtime error	49 ms	8164 KB	Execution failed because the return code was nonzero
75	Runtime error	53 ms	8304 KB	Execution failed because the return code was nonzero
76	Runtime error	48 ms	8268 KB	Execution failed because the return code was nonzero
77	Runtime error	47 ms	8384 KB	Execution failed because the return code was nonzero
78	Runtime error	48 ms	8116 KB	Execution failed because the return code was nonzero
79	Runtime error	48 ms	8212 KB	Execution failed because the return code was nonzero
80	Runtime error	51 ms	8200 KB	Execution failed because the return code was nonzero
81	Runtime error	48 ms	8148 KB	Execution failed because the return code was nonzero
82	Runtime error	49 ms	8364 KB	Execution failed because the return code was nonzero
83	Runtime error	48 ms	8156 KB	Execution failed because the return code was nonzero
84	Runtime error	49 ms	8404 KB	Execution failed because the return code was nonzero
85	Runtime error	51 ms	8272 KB	Execution failed because the return code was nonzero
86	Runtime error	58 ms	8196 KB	Execution failed because the return code was nonzero
87	Runtime error	48 ms	8180 KB	Execution failed because the return code was nonzero
88	Runtime error	47 ms	8456 KB	Execution failed because the return code was nonzero
89	Runtime error	47 ms	8216 KB	Execution failed because the return code was nonzero
90	Runtime error	49 ms	8284 KB	Execution failed because the return code was nonzero
91	Runtime error	48 ms	8084 KB	Execution failed because the return code was nonzero
92	Runtime error	49 ms	8276 KB	Execution failed because the return code was nonzero