| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 587489 |
2022-07-02T01:39:51 Z |
PikaChu999 |
Mecho (IOI09_mecho) |
Java 11 |
|
1000 ms |
38004 KB |
/*
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;
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
