답안 #587489

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587489	2022-07-02T01:39:51 Z	PikaChu999	Mecho (IOI09_mecho)	Java 11	67 / 100	1000 ms	38004 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; //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;
          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 mechoDist[denx][deny] != INF; 
  }
  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

67.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	8700 KB	Output is correct
2	Correct	57 ms	8304 KB	Output is correct
3	Correct	64 ms	8228 KB	Output is correct
4	Correct	59 ms	8400 KB	Output is correct
5	Correct	56 ms	8344 KB	Output is correct
6	Correct	57 ms	8488 KB	Output is correct
7	Execution timed out	1090 ms	32956 KB	Time limit exceeded
8	Correct	57 ms	8240 KB	Output is correct
9	Correct	105 ms	13936 KB	Output is correct
10	Correct	102 ms	14048 KB	Output is correct
11	Correct	107 ms	14128 KB	Output is correct
12	Correct	248 ms	15892 KB	Output is correct
13	Correct	304 ms	17564 KB	Output is correct
14	Correct	73 ms	8472 KB	Output is correct
15	Correct	113 ms	14600 KB	Output is correct
16	Correct	110 ms	14680 KB	Output is correct
17	Correct	113 ms	14160 KB	Output is correct
18	Correct	120 ms	13940 KB	Output is correct
19	Correct	160 ms	15120 KB	Output is correct
20	Correct	104 ms	13984 KB	Output is correct
21	Correct	310 ms	15588 KB	Output is correct
22	Correct	202 ms	15568 KB	Output is correct
23	Correct	273 ms	16492 KB	Output is correct
24	Correct	271 ms	15908 KB	Output is correct
25	Correct	347 ms	17524 KB	Output is correct
26	Correct	244 ms	16156 KB	Output is correct
27	Correct	340 ms	17476 KB	Output is correct
28	Correct	287 ms	17128 KB	Output is correct
29	Correct	345 ms	17168 KB	Output is correct
30	Correct	201 ms	17200 KB	Output is correct
31	Correct	446 ms	18316 KB	Output is correct
32	Correct	254 ms	17652 KB	Output is correct
33	Correct	650 ms	24488 KB	Output is correct
34	Correct	413 ms	22760 KB	Output is correct
35	Correct	534 ms	23412 KB	Output is correct
36	Correct	612 ms	23796 KB	Output is correct
37	Correct	427 ms	23512 KB	Output is correct
38	Correct	572 ms	23836 KB	Output is correct
39	Correct	685 ms	24280 KB	Output is correct
40	Correct	534 ms	24012 KB	Output is correct
41	Correct	762 ms	22976 KB	Output is correct
42	Correct	697 ms	25140 KB	Output is correct
43	Correct	534 ms	23804 KB	Output is correct
44	Correct	656 ms	24240 KB	Output is correct
45	Correct	719 ms	24988 KB	Output is correct
46	Correct	537 ms	24136 KB	Output is correct
47	Correct	757 ms	26000 KB	Output is correct
48	Correct	738 ms	28784 KB	Output is correct
49	Correct	536 ms	27032 KB	Output is correct
50	Correct	800 ms	27804 KB	Output is correct
51	Correct	800 ms	30548 KB	Output is correct
52	Correct	578 ms	29504 KB	Output is correct
53	Correct	840 ms	29668 KB	Output is correct
54	Correct	798 ms	29984 KB	Output is correct
55	Correct	658 ms	28852 KB	Output is correct
56	Correct	937 ms	28604 KB	Output is correct
57	Correct	872 ms	31644 KB	Output is correct
58	Correct	667 ms	30188 KB	Output is correct
59	Correct	992 ms	30344 KB	Output is correct
60	Correct	916 ms	33156 KB	Output is correct
61	Correct	743 ms	32560 KB	Output is correct
62	Execution timed out	1098 ms	32588 KB	Time limit exceeded
63	Execution timed out	1094 ms	34400 KB	Time limit exceeded
64	Execution timed out	1053 ms	35276 KB	Time limit exceeded
65	Execution timed out	1022 ms	35440 KB	Time limit exceeded
66	Execution timed out	1089 ms	36768 KB	Time limit exceeded
67	Correct	340 ms	24484 KB	Output is correct
68	Correct	953 ms	31656 KB	Output is correct
69	Correct	870 ms	35260 KB	Output is correct
70	Execution timed out	1006 ms	35036 KB	Time limit exceeded
71	Execution timed out	1018 ms	33688 KB	Time limit exceeded
72	Execution timed out	1080 ms	31148 KB	Time limit exceeded
73	Execution timed out	1044 ms	33912 KB	Time limit exceeded
74	Execution timed out	1030 ms	34564 KB	Time limit exceeded
75	Execution timed out	1072 ms	38004 KB	Time limit exceeded
76	Execution timed out	1074 ms	33876 KB	Time limit exceeded
77	Execution timed out	1084 ms	34648 KB	Time limit exceeded
78	Correct	318 ms	26580 KB	Output is correct
79	Execution timed out	1091 ms	37180 KB	Time limit exceeded
80	Execution timed out	1046 ms	36496 KB	Time limit exceeded
81	Execution timed out	1077 ms	36732 KB	Time limit exceeded
82	Execution timed out	1062 ms	36888 KB	Time limit exceeded
83	Execution timed out	1084 ms	37272 KB	Time limit exceeded
84	Execution timed out	1083 ms	33592 KB	Time limit exceeded
85	Execution timed out	1084 ms	37272 KB	Time limit exceeded
86	Execution timed out	1091 ms	37272 KB	Time limit exceeded
87	Execution timed out	1084 ms	33788 KB	Time limit exceeded
88	Execution timed out	1079 ms	33072 KB	Time limit exceeded
89	Execution timed out	1084 ms	37560 KB	Time limit exceeded
90	Execution timed out	1058 ms	33072 KB	Time limit exceeded
91	Execution timed out	1074 ms	33356 KB	Time limit exceeded
92	Execution timed out	1071 ms	37256 KB	Time limit exceeded