| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 587493 |
2022-07-02T01:43:56 Z |
Agnimandur |
Mecho (IOI09_mecho) |
Java 11 |
|
1000 ms |
38744 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/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;
}
}
| # |
Verdict |
Execution time |
Memory |
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 |
