Submission #587491

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
587491	2022-07-02T01:40:38 Z	Agnimandur	Mecho (IOI09_mecho)	Java 11	0 / 100	165 ms	12236 KB

mecho

/*
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT
 
1. Find shortest time it takes for the bees to reach every cell, and the shortest time it takes for Mecho to reach every cell (in minutes, take ceiling(steps it took for Mecho to get there (divided by) steps Mecho can take in a minute))
2. Binary search on the largest # of minutes that Mecho can eat honey for
*/
import java.util.*;
import java.io.*;
 
class Main{
  public static int n; 
  public static long s; 
  public static char[][] grid; //'T' = tree, 'G' = grass, 'M' = mecho, 'H' = beehive, 'D' = mecho's house
  //Neither bees or mecho can enter the tree cells
  //Mecho can travel s steps in 1 minute --> can reach a certain cell in ceil(steps it took to get to that cell/s) minutes, bees travel every minute 
  //Given that Mecho waited for x minutes, Mecho can visit a cell iff mecho[x][y] + x < bee[x][y] 
  
  public static int[] xcoors = {0,0,1,-1};
  public static int[] ycoors = {1,-1,0,0};
	public static int INF = 10000000;
 
  public static int denx; 
  public static int deny; //x y coordinates of mecho's house
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    StringTokenizer details = new StringTokenizer(br.readLine());
    n = Integer.parseInt(details.nextToken());
    s = Long.parseLong(details.nextToken());
    grid = new char[n][n]; 
 
    for(int a = 0; a < n; a++){
      String row = br.readLine(); 
      for(int b = 0; b < n; b++){
        grid[a][b] = row.charAt(b);
        if(grid[a][b] == 'D'){
          denx = a; 
          deny = b; 
        }
      }
    }
    
    int min = 0; 
    int max = n*n/2; //best case it takes the bees n*m time to reach Mecho/Mecho is able to evade the bees for n*m time
 
		if (!valid(0)) {
			System.out.println(-1);
		} else {
			while(min < max) {
        int mid = (min + max + 1)/2; 
        if(valid(mid)) min = mid; 
        else max = mid - 1; //want to maximize answer
      } 
      System.out.println(min);
		}
 
		//System.out.println(valid(3));
    br.close();
  }
  public static boolean valid(int headStart){ //how much head start the bees get
    ArrayDeque<Point> bees = new ArrayDeque<Point>(); 
    int[][] beeDist = new int[n][n]; 
    for(int[] row : beeDist) Arrays.fill(row, INF);
    ArrayDeque<Point> mecho = new ArrayDeque<Point>(); 
    int[][] mechoDist = new int[n][n]; 
    for(int[] row : mechoDist) Arrays.fill(row, INF);
    for(int a = 0; a < n; a++){
      for(int b = 0; b < n; b++){
        if(grid[a][b] == 'H'){
          bees.add(new Point(a,b));
          beeDist[a][b] = 0; 
        }
        else if(grid[a][b] == 'M'){
          mecho.add(new Point(a, b));
          mechoDist[a][b] = 0; 
        }
      }
    }
 
    //give bees headstart
    while(!bees.isEmpty()){
      Point cur = bees.peekFirst(); 
      if(beeDist[cur.x][cur.y] == headStart) break;
			bees.pollFirst();
			
      for(int a = 0; a < 4; a++){
        int xc = xcoors[a] + cur.x;
        int yc = ycoors[a] + cur.y; 
        if(outOfBounds(xc, yc) || beeDist[xc][yc] != INF || grid[xc][yc] == 'T' || grid[xc][yc] == 'D') continue;
        beeDist[xc][yc] = beeDist[cur.x][cur.y] + 1; 
        bees.add(new Point(xc, yc));
      }
    }
 
    //now do simultaneous mecho and bees bfs
    int round = 1; //mecho can be up to round * s steps away from starting point
    while(!mecho.isEmpty()){
      //mecho moves
      while(!mecho.isEmpty()){
        Point cur = mecho.peekFirst(); 
        if(mechoDist[cur.x][cur.y] >= round * s) break;
				mecho.pollFirst();
				if (beeDist[cur.x][cur.y] != INF) {
					//this cell has already been taken over by the bees, so Mecho cannot be here.
					continue;
				}
				
        for(int a = 0; a < 4; a++){
          int xc = xcoors[a] + cur.x;
          int yc = ycoors[a] + cur.y; 
          if(outOfBounds(xc, yc) || beeDist[xc][yc] != INF || mechoDist[xc][yc] != INF || grid[xc][yc] == 'T' || grid[xc][yc] == 'H') continue; 
          mechoDist[xc][yc] = mechoDist[cur.x][cur.y] + 1;
          if (mechoDist[denx][deny] != INF) return true; 
          mecho.add(new Point(xc, yc));
        }
      }
      //bees move
      while(!bees.isEmpty()){
        Point cur = bees.peekFirst(); 
        if(beeDist[cur.x][cur.y] >= headStart + round) break; 
        bees.pollFirst(); 
        for(int a = 0; a < 4; a++){
          int xc = xcoors[a] + cur.x; 
          int yc = ycoors[a] + cur.y; 
          if(outOfBounds(xc, yc) || beeDist[xc][yc] != INF || grid[xc][yc] == 'T' || grid[xc][yc] == 'D') continue; 
          beeDist[xc][yc] = beeDist[cur.x][cur.y] + 1; 
          bees.add(new Point(xc, yc));
        }
      }
			
      round++; 
    }
    return false; 
  }
  public static boolean outOfBounds(int x, int y){
    if(x < 0 || y < 0 || x >= n || y >= n) return true; 
    return false; 
  }
 
 
	public static void debug(int[][] dist) {
  	for (int i = 0; i < n; i++) {
  		for (int j = 0; j < n; j++) {
  			if (dist[i][j] == INF)
  				System.out.print("I");
  			else
  				System.out.print(dist[i][j]);
  		}
  		System.out.println();
  	}
  }
}
 
class Point{
  int x; 
  int y; 
  public Point(int xc, int yc){
    x = xc; 
    y = yc; 
  }
  public String toString(){
    return x + " " + y; 
  }
}

Subtask #1

0.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	144 ms	12080 KB	Execution failed because the return code was nonzero
2	Runtime error	152 ms	11936 KB	Execution failed because the return code was nonzero
3	Runtime error	140 ms	12100 KB	Execution failed because the return code was nonzero
4	Runtime error	151 ms	12032 KB	Execution failed because the return code was nonzero
5	Runtime error	148 ms	11992 KB	Execution failed because the return code was nonzero
6	Runtime error	135 ms	11844 KB	Execution failed because the return code was nonzero
7	Runtime error	142 ms	12000 KB	Execution failed because the return code was nonzero
8	Runtime error	141 ms	11916 KB	Execution failed because the return code was nonzero
9	Runtime error	137 ms	12060 KB	Execution failed because the return code was nonzero
10	Runtime error	146 ms	11880 KB	Execution failed because the return code was nonzero
11	Runtime error	141 ms	11856 KB	Execution failed because the return code was nonzero
12	Runtime error	148 ms	11920 KB	Execution failed because the return code was nonzero
13	Runtime error	145 ms	11944 KB	Execution failed because the return code was nonzero
14	Runtime error	135 ms	11944 KB	Execution failed because the return code was nonzero
15	Runtime error	150 ms	11888 KB	Execution failed because the return code was nonzero
16	Runtime error	157 ms	12028 KB	Execution failed because the return code was nonzero
17	Runtime error	142 ms	12000 KB	Execution failed because the return code was nonzero
18	Runtime error	146 ms	11928 KB	Execution failed because the return code was nonzero
19	Runtime error	144 ms	11964 KB	Execution failed because the return code was nonzero
20	Runtime error	142 ms	11756 KB	Execution failed because the return code was nonzero
21	Runtime error	137 ms	12004 KB	Execution failed because the return code was nonzero
22	Runtime error	143 ms	11884 KB	Execution failed because the return code was nonzero
23	Runtime error	153 ms	12012 KB	Execution failed because the return code was nonzero
24	Runtime error	135 ms	11840 KB	Execution failed because the return code was nonzero
25	Runtime error	142 ms	12016 KB	Execution failed because the return code was nonzero
26	Runtime error	135 ms	12040 KB	Execution failed because the return code was nonzero
27	Runtime error	165 ms	11944 KB	Execution failed because the return code was nonzero
28	Runtime error	146 ms	12148 KB	Execution failed because the return code was nonzero
29	Runtime error	142 ms	11864 KB	Execution failed because the return code was nonzero
30	Runtime error	135 ms	11844 KB	Execution failed because the return code was nonzero
31	Runtime error	136 ms	11984 KB	Execution failed because the return code was nonzero
32	Runtime error	145 ms	11808 KB	Execution failed because the return code was nonzero
33	Runtime error	144 ms	12184 KB	Execution failed because the return code was nonzero
34	Runtime error	133 ms	12156 KB	Execution failed because the return code was nonzero
35	Runtime error	138 ms	12024 KB	Execution failed because the return code was nonzero
36	Runtime error	133 ms	12008 KB	Execution failed because the return code was nonzero
37	Runtime error	139 ms	12016 KB	Execution failed because the return code was nonzero
38	Runtime error	134 ms	11944 KB	Execution failed because the return code was nonzero
39	Runtime error	133 ms	12076 KB	Execution failed because the return code was nonzero
40	Runtime error	137 ms	12080 KB	Execution failed because the return code was nonzero
41	Runtime error	138 ms	12048 KB	Execution failed because the return code was nonzero
42	Runtime error	139 ms	11960 KB	Execution failed because the return code was nonzero
43	Runtime error	138 ms	12096 KB	Execution failed because the return code was nonzero
44	Runtime error	131 ms	12052 KB	Execution failed because the return code was nonzero
45	Runtime error	139 ms	11792 KB	Execution failed because the return code was nonzero
46	Runtime error	134 ms	12216 KB	Execution failed because the return code was nonzero
47	Runtime error	137 ms	12008 KB	Execution failed because the return code was nonzero
48	Runtime error	133 ms	12024 KB	Execution failed because the return code was nonzero
49	Runtime error	131 ms	11800 KB	Execution failed because the return code was nonzero
50	Runtime error	135 ms	12016 KB	Execution failed because the return code was nonzero
51	Runtime error	146 ms	12144 KB	Execution failed because the return code was nonzero
52	Runtime error	140 ms	11872 KB	Execution failed because the return code was nonzero
53	Runtime error	140 ms	12120 KB	Execution failed because the return code was nonzero
54	Runtime error	148 ms	11952 KB	Execution failed because the return code was nonzero
55	Runtime error	135 ms	12060 KB	Execution failed because the return code was nonzero
56	Runtime error	135 ms	11984 KB	Execution failed because the return code was nonzero
57	Runtime error	131 ms	12060 KB	Execution failed because the return code was nonzero
58	Runtime error	141 ms	12032 KB	Execution failed because the return code was nonzero
59	Runtime error	134 ms	11940 KB	Execution failed because the return code was nonzero
60	Runtime error	147 ms	12172 KB	Execution failed because the return code was nonzero
61	Runtime error	133 ms	11984 KB	Execution failed because the return code was nonzero
62	Runtime error	152 ms	11768 KB	Execution failed because the return code was nonzero
63	Runtime error	135 ms	12000 KB	Execution failed because the return code was nonzero
64	Runtime error	145 ms	12236 KB	Execution failed because the return code was nonzero
65	Runtime error	132 ms	12088 KB	Execution failed because the return code was nonzero
66	Runtime error	145 ms	12084 KB	Execution failed because the return code was nonzero
67	Runtime error	134 ms	12004 KB	Execution failed because the return code was nonzero
68	Runtime error	146 ms	11916 KB	Execution failed because the return code was nonzero
69	Runtime error	136 ms	11952 KB	Execution failed because the return code was nonzero
70	Runtime error	133 ms	11848 KB	Execution failed because the return code was nonzero
71	Runtime error	143 ms	12140 KB	Execution failed because the return code was nonzero
72	Runtime error	136 ms	11768 KB	Execution failed because the return code was nonzero
73	Runtime error	149 ms	11876 KB	Execution failed because the return code was nonzero
74	Runtime error	131 ms	12060 KB	Execution failed because the return code was nonzero
75	Runtime error	134 ms	11836 KB	Execution failed because the return code was nonzero
76	Runtime error	135 ms	12164 KB	Execution failed because the return code was nonzero
77	Runtime error	139 ms	11924 KB	Execution failed because the return code was nonzero
78	Runtime error	141 ms	11896 KB	Execution failed because the return code was nonzero
79	Runtime error	142 ms	11884 KB	Execution failed because the return code was nonzero
80	Runtime error	137 ms	11816 KB	Execution failed because the return code was nonzero
81	Runtime error	139 ms	12012 KB	Execution failed because the return code was nonzero
82	Runtime error	135 ms	12012 KB	Execution failed because the return code was nonzero
83	Runtime error	136 ms	11980 KB	Execution failed because the return code was nonzero
84	Runtime error	130 ms	11944 KB	Execution failed because the return code was nonzero
85	Runtime error	138 ms	12024 KB	Execution failed because the return code was nonzero
86	Runtime error	133 ms	12172 KB	Execution failed because the return code was nonzero
87	Runtime error	134 ms	12020 KB	Execution failed because the return code was nonzero
88	Runtime error	146 ms	11952 KB	Execution failed because the return code was nonzero
89	Runtime error	137 ms	12084 KB	Execution failed because the return code was nonzero
90	Runtime error	153 ms	11920 KB	Execution failed because the return code was nonzero
91	Runtime error	143 ms	11896 KB	Execution failed because the return code was nonzero
92	Runtime error	130 ms	12232 KB	Execution failed because the return code was nonzero