답안 #587493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587493	2022-07-02T01:43:56 Z	Agnimandur	Mecho (IOI09_mecho)	Java 11	61 / 100	1000 ms	38744 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.*;
 
public class mecho {
  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; 
  }
}

Subtask #1

61.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	8316 KB	Output is correct
2	Correct	69 ms	8112 KB	Output is correct
3	Correct	69 ms	8384 KB	Output is correct
4	Correct	71 ms	8116 KB	Output is correct
5	Correct	71 ms	8288 KB	Output is correct
6	Correct	66 ms	8304 KB	Output is correct
7	Execution timed out	1028 ms	32752 KB	Time limit exceeded
8	Correct	77 ms	8216 KB	Output is correct
9	Correct	83 ms	8144 KB	Output is correct
10	Correct	82 ms	8076 KB	Output is correct
11	Correct	76 ms	8124 KB	Output is correct
12	Correct	194 ms	15548 KB	Output is correct
13	Correct	406 ms	18060 KB	Output is correct
14	Correct	97 ms	8292 KB	Output is correct
15	Correct	80 ms	8228 KB	Output is correct
16	Correct	135 ms	14424 KB	Output is correct
17	Correct	133 ms	14396 KB	Output is correct
18	Correct	130 ms	14608 KB	Output is correct
19	Correct	132 ms	14528 KB	Output is correct
20	Correct	143 ms	13980 KB	Output is correct
21	Correct	218 ms	15380 KB	Output is correct
22	Correct	247 ms	15580 KB	Output is correct
23	Correct	288 ms	16548 KB	Output is correct
24	Correct	257 ms	15944 KB	Output is correct
25	Correct	197 ms	16072 KB	Output is correct
26	Correct	346 ms	16748 KB	Output is correct
27	Correct	249 ms	16148 KB	Output is correct
28	Correct	324 ms	16456 KB	Output is correct
29	Correct	293 ms	16832 KB	Output is correct
30	Correct	403 ms	17180 KB	Output is correct
31	Correct	387 ms	17204 KB	Output is correct
32	Correct	384 ms	17368 KB	Output is correct
33	Correct	442 ms	23184 KB	Output is correct
34	Correct	451 ms	23164 KB	Output is correct
35	Correct	578 ms	23540 KB	Output is correct
36	Correct	582 ms	24292 KB	Output is correct
37	Correct	479 ms	23952 KB	Output is correct
38	Correct	608 ms	24056 KB	Output is correct
39	Correct	539 ms	24240 KB	Output is correct
40	Correct	502 ms	24600 KB	Output is correct
41	Correct	694 ms	23328 KB	Output is correct
42	Correct	623 ms	24664 KB	Output is correct
43	Correct	533 ms	24424 KB	Output is correct
44	Correct	728 ms	24312 KB	Output is correct
45	Correct	592 ms	26148 KB	Output is correct
46	Correct	587 ms	25592 KB	Output is correct
47	Correct	782 ms	26148 KB	Output is correct
48	Correct	658 ms	28012 KB	Output is correct
49	Correct	595 ms	27496 KB	Output is correct
50	Correct	895 ms	27992 KB	Output is correct
51	Correct	638 ms	30044 KB	Output is correct
52	Correct	629 ms	29848 KB	Output is correct
53	Correct	901 ms	30384 KB	Output is correct
54	Correct	762 ms	30804 KB	Output is correct
55	Correct	696 ms	29792 KB	Output is correct
56	Execution timed out	1025 ms	29304 KB	Time limit exceeded
57	Correct	703 ms	30604 KB	Output is correct
58	Correct	735 ms	30668 KB	Output is correct
59	Execution timed out	1064 ms	30528 KB	Time limit exceeded
60	Correct	814 ms	35088 KB	Output is correct
61	Correct	805 ms	34024 KB	Output is correct
62	Execution timed out	1089 ms	32444 KB	Time limit exceeded
63	Execution timed out	1063 ms	36360 KB	Time limit exceeded
64	Execution timed out	1078 ms	35488 KB	Time limit exceeded
65	Execution timed out	1041 ms	36604 KB	Time limit exceeded
66	Execution timed out	1064 ms	36156 KB	Time limit exceeded
67	Correct	354 ms	24592 KB	Output is correct
68	Execution timed out	1018 ms	31972 KB	Time limit exceeded
69	Correct	886 ms	34172 KB	Output is correct
70	Execution timed out	1014 ms	33960 KB	Time limit exceeded
71	Execution timed out	1029 ms	33652 KB	Time limit exceeded
72	Correct	969 ms	31000 KB	Output is correct
73	Execution timed out	1091 ms	38292 KB	Time limit exceeded
74	Execution timed out	1088 ms	36920 KB	Time limit exceeded
75	Execution timed out	1089 ms	38744 KB	Time limit exceeded
76	Execution timed out	1091 ms	34820 KB	Time limit exceeded
77	Execution timed out	1094 ms	38556 KB	Time limit exceeded
78	Correct	326 ms	26736 KB	Output is correct
79	Execution timed out	1080 ms	37076 KB	Time limit exceeded
80	Execution timed out	1094 ms	37136 KB	Time limit exceeded
81	Execution timed out	1098 ms	38408 KB	Time limit exceeded
82	Execution timed out	1071 ms	33876 KB	Time limit exceeded
83	Execution timed out	1096 ms	37184 KB	Time limit exceeded
84	Execution timed out	1093 ms	33992 KB	Time limit exceeded
85	Execution timed out	1078 ms	37500 KB	Time limit exceeded
86	Execution timed out	1082 ms	37548 KB	Time limit exceeded
87	Execution timed out	1089 ms	34412 KB	Time limit exceeded
88	Execution timed out	1078 ms	37440 KB	Time limit exceeded
89	Execution timed out	1089 ms	37308 KB	Time limit exceeded
90	Execution timed out	1066 ms	33104 KB	Time limit exceeded
91	Execution timed out	1088 ms	32960 KB	Time limit exceeded
92	Execution timed out	1085 ms	37640 KB	Time limit exceeded