# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
74404 |
2018-08-31T16:09:41 Z |
vvv3334 |
Mecho (IOI09_mecho) |
C++14 |
|
287 ms |
22268 KB |
/**
* A binary search solution for IOI 2009 problem "mecho"
*
* This solution should score 100%
*
* Carl Hultquist, [email protected]
*/
#include <string.h>
#include <iostream>
#include <string>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <utility>
#include <deque>
using namespace std;
#define MAX_N 2000
int cx[4] = {1, -1, 0, 0};
int cy[4] = {0, 0, 1, -1};
char mainMap[MAX_N][MAX_N];
bool reachable[MAX_N][MAX_N];
// The time that it takes the bees to reach any cell in the map
int beeDistance[MAX_N][MAX_N];
int n, s;
int dx, dy;
int mx, my;
/**
* Tests if Mecho is able to reach his home after staying with
* the honey for the given delay time.
*/
bool test(int delay)
{
// Check if the bees catch Mecho whilst he is still with
// the honey.
if (delay * s >= beeDistance[mx][my])
return false;
// Initialise data structures -- at the beginning of the search,
// Mecho has only reached the cell with the honey. Note that it
// is possible for the bees to catch Mecho at the honey -- but
// we checked for this case above, and so if we reach this point
// we know that Mecho is safe with the honey after the given
// delay.
memset(reachable, 0, sizeof(reachable));
deque<pair<int, pair<int, int> > > q;
q.push_back(make_pair(delay * s, make_pair(mx, my)));
reachable[mx][my] = true;
// Now do the main loop to see what other cells Mecho can reach.
while (!q.empty())
{
int distance = q.front().first;
int x = q.front().second.first;
int y = q.front().second.second;
q.pop_front();
// If Mecho has reached his home, then we are done.
if (mainMap[x][y] == 'D')
return true;
// Check neighbouring cells
for (int c = 0; c < 4; c++)
{
int nx = x + cx[c];
int ny = y + cy[c];
// Check that the cell is valid, that it is not a tree, and
// that Mecho can get here before the bees.
if (nx < 0 || nx >= n || ny < 0 || ny >= n || mainMap[nx][ny] == 'T' || (distance + 1) >= beeDistance[nx][ny] || reachable[nx][ny])
continue;
// All OK, so add it to the queue
q.push_back(make_pair(distance + 1, make_pair(nx, ny)));
reachable[nx][ny] = true;
}
}
// If we reach here, then Mecho was unable to reach his home.
return false;
}
int main(int argc, char **argv)
{
// Read in the data
cin >> n >> s;
deque<pair<int, int> > bq;
memset(beeDistance, -1, sizeof(beeDistance));
for (int i = 0; i < n; i++)
{
cin >> ws;
for (int j = 0; j < n; j++)
{
cin >> mainMap[i][j];
if (mainMap[i][j] == 'H')
{
bq.push_back(make_pair(i, j));
beeDistance[i][j] = 0;
}
else if (mainMap[i][j] == 'M')
{
mx = i;
my = j;
// Bees can travel through the location of the honey
mainMap[i][j] = 'G';
}
else if (mainMap[i][j] == 'D')
{
dx = i;
dy = j;
}
}
}
// Precompute the time that it takes the bees to reach any other
// cell in the map.
while (!bq.empty())
{
int x = bq.front().first;
int y = bq.front().second;
bq.pop_front();
for (int c = 0; c < 4; c++)
{
int nx = x + cx[c];
int ny = y + cy[c];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || mainMap[nx][ny] != 'G' || beeDistance[nx][ny] != -1)
continue;
beeDistance[nx][ny] = beeDistance[x][y] + s;
bq.push_back(make_pair(nx, ny));
}
}
// The bees can never enter Mecho's home, so set this to a large
// sentinel value.
beeDistance[dx][dy] = n * n * s;
// Binary search to find the maximum delay time.
int low = -1, high = 2 * n * n;
while (high - low > 1)
{
int mid = (low + high) >> 1;
if (test(mid))
low = mid;
else
high = mid;
}
cout << low << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
19832 KB |
Output is correct |
2 |
Correct |
17 ms |
19956 KB |
Output is correct |
3 |
Correct |
17 ms |
19956 KB |
Output is correct |
4 |
Correct |
18 ms |
20104 KB |
Output is correct |
5 |
Correct |
20 ms |
20104 KB |
Output is correct |
6 |
Correct |
18 ms |
20108 KB |
Output is correct |
7 |
Correct |
170 ms |
21664 KB |
Output is correct |
8 |
Correct |
18 ms |
21664 KB |
Output is correct |
9 |
Correct |
19 ms |
21664 KB |
Output is correct |
10 |
Correct |
20 ms |
21664 KB |
Output is correct |
11 |
Correct |
18 ms |
21664 KB |
Output is correct |
12 |
Correct |
20 ms |
21664 KB |
Output is correct |
13 |
Correct |
17 ms |
21664 KB |
Output is correct |
14 |
Correct |
19 ms |
21664 KB |
Output is correct |
15 |
Correct |
18 ms |
21664 KB |
Output is correct |
16 |
Correct |
18 ms |
21664 KB |
Output is correct |
17 |
Correct |
19 ms |
21664 KB |
Output is correct |
18 |
Correct |
20 ms |
21664 KB |
Output is correct |
19 |
Correct |
18 ms |
21664 KB |
Output is correct |
20 |
Correct |
18 ms |
21664 KB |
Output is correct |
21 |
Correct |
19 ms |
21664 KB |
Output is correct |
22 |
Correct |
18 ms |
21664 KB |
Output is correct |
23 |
Correct |
19 ms |
21664 KB |
Output is correct |
24 |
Correct |
18 ms |
21664 KB |
Output is correct |
25 |
Correct |
19 ms |
21664 KB |
Output is correct |
26 |
Correct |
19 ms |
21664 KB |
Output is correct |
27 |
Correct |
18 ms |
21664 KB |
Output is correct |
28 |
Correct |
20 ms |
21664 KB |
Output is correct |
29 |
Correct |
20 ms |
21664 KB |
Output is correct |
30 |
Correct |
19 ms |
21664 KB |
Output is correct |
31 |
Correct |
19 ms |
21664 KB |
Output is correct |
32 |
Correct |
19 ms |
21664 KB |
Output is correct |
33 |
Correct |
29 ms |
21664 KB |
Output is correct |
34 |
Correct |
28 ms |
21664 KB |
Output is correct |
35 |
Correct |
49 ms |
21664 KB |
Output is correct |
36 |
Correct |
32 ms |
21664 KB |
Output is correct |
37 |
Correct |
32 ms |
21664 KB |
Output is correct |
38 |
Correct |
56 ms |
21664 KB |
Output is correct |
39 |
Correct |
36 ms |
21664 KB |
Output is correct |
40 |
Correct |
36 ms |
21664 KB |
Output is correct |
41 |
Correct |
69 ms |
21664 KB |
Output is correct |
42 |
Correct |
40 ms |
21664 KB |
Output is correct |
43 |
Correct |
42 ms |
21664 KB |
Output is correct |
44 |
Correct |
83 ms |
21664 KB |
Output is correct |
45 |
Correct |
50 ms |
21664 KB |
Output is correct |
46 |
Correct |
43 ms |
21664 KB |
Output is correct |
47 |
Correct |
95 ms |
21664 KB |
Output is correct |
48 |
Correct |
48 ms |
21664 KB |
Output is correct |
49 |
Correct |
47 ms |
21664 KB |
Output is correct |
50 |
Correct |
109 ms |
21664 KB |
Output is correct |
51 |
Correct |
52 ms |
21664 KB |
Output is correct |
52 |
Correct |
51 ms |
21664 KB |
Output is correct |
53 |
Correct |
123 ms |
21664 KB |
Output is correct |
54 |
Correct |
63 ms |
21664 KB |
Output is correct |
55 |
Correct |
59 ms |
21664 KB |
Output is correct |
56 |
Correct |
163 ms |
21664 KB |
Output is correct |
57 |
Correct |
66 ms |
21664 KB |
Output is correct |
58 |
Correct |
77 ms |
21664 KB |
Output is correct |
59 |
Correct |
194 ms |
21708 KB |
Output is correct |
60 |
Correct |
78 ms |
21708 KB |
Output is correct |
61 |
Correct |
108 ms |
21756 KB |
Output is correct |
62 |
Correct |
211 ms |
21756 KB |
Output is correct |
63 |
Correct |
161 ms |
21756 KB |
Output is correct |
64 |
Correct |
287 ms |
21756 KB |
Output is correct |
65 |
Correct |
222 ms |
21756 KB |
Output is correct |
66 |
Correct |
194 ms |
21756 KB |
Output is correct |
67 |
Correct |
177 ms |
21764 KB |
Output is correct |
68 |
Correct |
104 ms |
21764 KB |
Output is correct |
69 |
Correct |
127 ms |
21888 KB |
Output is correct |
70 |
Correct |
89 ms |
21888 KB |
Output is correct |
71 |
Correct |
97 ms |
21888 KB |
Output is correct |
72 |
Correct |
87 ms |
21888 KB |
Output is correct |
73 |
Correct |
94 ms |
21944 KB |
Output is correct |
74 |
Correct |
143 ms |
22004 KB |
Output is correct |
75 |
Correct |
135 ms |
22012 KB |
Output is correct |
76 |
Correct |
128 ms |
22012 KB |
Output is correct |
77 |
Correct |
140 ms |
22268 KB |
Output is correct |
78 |
Correct |
144 ms |
22268 KB |
Output is correct |
79 |
Correct |
110 ms |
22268 KB |
Output is correct |
80 |
Correct |
153 ms |
22268 KB |
Output is correct |
81 |
Correct |
136 ms |
22268 KB |
Output is correct |
82 |
Correct |
122 ms |
22268 KB |
Output is correct |
83 |
Correct |
148 ms |
22268 KB |
Output is correct |
84 |
Correct |
136 ms |
22268 KB |
Output is correct |
85 |
Correct |
146 ms |
22268 KB |
Output is correct |
86 |
Correct |
145 ms |
22268 KB |
Output is correct |
87 |
Correct |
140 ms |
22268 KB |
Output is correct |
88 |
Correct |
174 ms |
22268 KB |
Output is correct |
89 |
Correct |
152 ms |
22268 KB |
Output is correct |
90 |
Correct |
156 ms |
22268 KB |
Output is correct |
91 |
Correct |
156 ms |
22268 KB |
Output is correct |
92 |
Correct |
161 ms |
22268 KB |
Output is correct |