Submission #51597

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51597	2018-06-19T03:02:03 Z	model_code	Mecho (IOI09_mecho)	C++	46 / 100	20 ms	1420 KB

mecho

/**
 * A binary search solution for IOI 2009 problem "mecho"
 *
 * This solution should score 100%
 *
 * Carl Hultquist, [email protected]
 */

#include <iostream>
#include <string>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <utility>
#include <memory.h>
#include <deque>

using namespace std;

#define MAX_N 200

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;
}

Subtask #1

46.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	2 ms	536 KB	Output is correct
4	Correct	2 ms	588 KB	Output is correct
5	Correct	2 ms	652 KB	Output is correct
6	Correct	2 ms	652 KB	Output is correct
7	Runtime error	13 ms	1028 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Correct	2 ms	1092 KB	Output is correct
9	Correct	2 ms	1092 KB	Output is correct
10	Correct	2 ms	1092 KB	Output is correct
11	Correct	2 ms	1220 KB	Output is correct
12	Correct	2 ms	1220 KB	Output is correct
13	Correct	2 ms	1220 KB	Output is correct
14	Correct	3 ms	1220 KB	Output is correct
15	Correct	2 ms	1220 KB	Output is correct
16	Correct	2 ms	1220 KB	Output is correct
17	Correct	2 ms	1220 KB	Output is correct
18	Correct	2 ms	1220 KB	Output is correct
19	Correct	2 ms	1220 KB	Output is correct
20	Correct	2 ms	1220 KB	Output is correct
21	Correct	2 ms	1220 KB	Output is correct
22	Correct	3 ms	1220 KB	Output is correct
23	Correct	3 ms	1220 KB	Output is correct
24	Correct	2 ms	1220 KB	Output is correct
25	Correct	3 ms	1220 KB	Output is correct
26	Correct	3 ms	1220 KB	Output is correct
27	Correct	3 ms	1220 KB	Output is correct
28	Correct	3 ms	1220 KB	Output is correct
29	Correct	2 ms	1220 KB	Output is correct
30	Correct	3 ms	1220 KB	Output is correct
31	Correct	3 ms	1220 KB	Output is correct
32	Correct	3 ms	1220 KB	Output is correct
33	Runtime error	8 ms	1220 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
34	Runtime error	8 ms	1220 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
35	Runtime error	10 ms	1256 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
36	Runtime error	8 ms	1256 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
37	Runtime error	10 ms	1256 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
38	Runtime error	8 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
39	Runtime error	10 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Runtime error	9 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
41	Runtime error	9 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Runtime error	14 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
43	Runtime error	9 ms	1272 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
44	Runtime error	9 ms	1276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
45	Runtime error	10 ms	1276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
46	Runtime error	16 ms	1276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
47	Runtime error	12 ms	1276 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
48	Runtime error	12 ms	1308 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
49	Runtime error	11 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
50	Runtime error	11 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
51	Runtime error	12 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
52	Runtime error	11 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
53	Runtime error	12 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
54	Runtime error	12 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
55	Runtime error	14 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	12 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	13 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	13 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	14 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	14 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	14 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	15 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	15 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	16 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	15 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	15 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	16 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	15 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	14 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Runtime error	13 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
71	Runtime error	18 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
72	Runtime error	17 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
73	Runtime error	15 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
74	Runtime error	16 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
75	Runtime error	20 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
76	Runtime error	18 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
77	Runtime error	17 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
78	Runtime error	16 ms	1340 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
79	Runtime error	15 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
80	Runtime error	13 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
81	Runtime error	14 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Runtime error	14 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
83	Runtime error	14 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
84	Runtime error	13 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
85	Runtime error	17 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
86	Runtime error	13 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
87	Runtime error	13 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
88	Runtime error	19 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Runtime error	15 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
90	Runtime error	14 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
91	Runtime error	14 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Runtime error	13 ms	1420 KB	Execution killed with signal 11 (could be triggered by violating memory limits)