Submission #724717

#	Time	Username	Problem	Language	Result	Execution time	Memory
724717		rastervc	Mecho (IOI09_mecho)	C++17	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

mecho

**
 * A binary search solution for IOI 2009 problem "mecho"
 *
 * This solution should score 100%
 *
 * Carl Hultquist, chultquist@gmail.com
 */
 
#include <iostream>
#include <string>
#include <cstdlib>
#include <fstream>
#include <vector>
#include <utility>
#include <memory.h>
#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;
}

Compilation message (stderr)

mecho.cpp:6:30: error: stray '@' in program
    6 |  * Carl Hultquist, chultquist@gmail.com
      |                              ^
mecho.cpp:2:6: error: expected constructor, destructor, or type conversion before 'binary'
    2 |  * A binary search solution for IOI 2009 problem "mecho"
      |      ^~~~~~
In file included from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/bits/postypes.h:98:11: error: 'ptrdiff_t' does not name a type
   98 |   typedef ptrdiff_t streamsize; // Signed integral type
      |           ^~~~~~~~~
/usr/include/c++/10/bits/postypes.h:41:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; did you forget to '#include <cstddef>'?
   40 | #include <cwchar> // For mbstate_t
  +++ |+#include <cstddef>
   41 | 
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:126:26: error: declaration of 'operator new' as non-function
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/10/new:126:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  126 | _GLIBCXX_NODISCARD void* operator new(std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:127:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  127 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/10/new:128:26: error: declaration of 'operator new []' as non-function
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                          ^~~~~~~~
/usr/include/c++/10/new:128:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  128 | _GLIBCXX_NODISCARD void* operator new[](std::size_t) _GLIBCXX_THROW (std::bad_alloc)
      |                                              ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:129:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  129 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/10/new:135:29: error: 'std::size_t' has not been declared
  135 | void operator delete(void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                             ^~~
/usr/include/c++/10/new:137:31: error: 'std::size_t' has not been declared
  137 | void operator delete[](void*, std::size_t) _GLIBCXX_USE_NOEXCEPT
      |                               ^~~
/usr/include/c++/10/new:140:26: error: declaration of 'operator new' as non-function
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/10/new:140:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:140:52: error: expected primary-expression before 'const'
  140 | _GLIBCXX_NODISCARD void* operator new(std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                    ^~~~~
/usr/include/c++/10/new:142:26: error: declaration of 'operator new []' as non-function
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                          ^~~~~~~~
/usr/include/c++/10/new:142:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                              ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:142:54: error: expected primary-expression before 'const'
  142 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, const std::nothrow_t&) _GLIBCXX_USE_NOEXCEPT
      |                                                      ^~~~~
/usr/include/c++/10/new:149:26: error: declaration of 'operator new' as non-function
  149 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                          ^~~~~~~~
/usr/include/c++/10/new:149:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  149 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:149:68: error: expected primary-expression before ')' token
  149 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t)
      |                                                                    ^
/usr/include/c++/10/new:150:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  150 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/10/new:151:26: error: declaration of 'operator new' as non-function
  151 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                          ^~~~~~~~
/usr/include/c++/10/new:151:44: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  151 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                            ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:151:68: error: expected primary-expression before ',' token
  151 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                                                    ^
/usr/include/c++/10/new:151:70: error: expected primary-expression before 'const'
  151 | _GLIBCXX_NODISCARD void* operator new(std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                                                      ^~~~~
/usr/include/c++/10/new:157:26: error: declaration of 'operator new []' as non-function
  157 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
      |                          ^~~~~~~~
/usr/include/c++/10/new:157:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  157 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
      |                                              ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:157:70: error: expected primary-expression before ')' token
  157 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t)
      |                                                                      ^
/usr/include/c++/10/new:158:41: error: attributes after parenthesized initializer ignored [-fpermissive]
  158 |   __attribute__((__externally_visible__));
      |                                         ^
/usr/include/c++/10/new:159:26: error: declaration of 'operator new []' as non-function
  159 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
      |                          ^~~~~~~~
/usr/include/c++/10/new:159:46: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  159 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                              ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:159:70: error: expected primary-expression before ',' token
  159 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                                                      ^
/usr/include/c++/10/new:159:72: error: expected primary-expression before 'const'
  159 | _GLIBCXX_NODISCARD void* operator new[](std::size_t, std::align_val_t, const std::nothrow_t&)
      |                                                                        ^~~~~
/usr/include/c++/10/new:166:29: error: 'std::size_t' has not been declared
  166 | void operator delete(void*, std::size_t, std::align_val_t)
      |                             ^~~
/usr/include/c++/10/new:168:31: error: 'std::size_t' has not been declared
  168 | void operator delete[](void*, std::size_t, std::align_val_t)
      |                               ^~~
/usr/include/c++/10/new:174:33: error: declaration of 'operator new' as non-function
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                 ^~~~~~~~
/usr/include/c++/10/new:174:51: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                   ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:174:59: error: expected primary-expression before 'void'
  174 | _GLIBCXX_NODISCARD inline void* operator new(std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                           ^~~~
/usr/include/c++/10/new:176:33: error: declaration of 'operator new []' as non-function
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                 ^~~~~~~~
/usr/include/c++/10/new:176:53: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                     ^~~~~~
In file included from /usr/include/wchar.h:35,
                 from /usr/include/c++/10/cwchar:44,
                 from /usr/include/c++/10/bits/postypes.h:40,
                 from /usr/include/c++/10/iosfwd:40,
                 from /usr/include/c++/10/ios:38,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/lib/gcc/x86_64-linux-gnu/10/include/stddef.h:209:23: note: 'size_t' declared here
  209 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
In file included from /usr/include/c++/10/bits/exception_ptr.h:40,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:9:
/usr/include/c++/10/new:176:61: error: expected primary-expression before 'void'
  176 | _GLIBCXX_NODISCARD inline void* operator new[](std::size_t, void* __p) _GLIBCXX_USE_NOEXCEPT
      |                                                             ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39