Submission #886610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886610	2023-12-12T12:11:45 Z	gnu	Mecho (IOI09_mecho)	C++17	Compilation error	0 ms	0 KB

mecho

#include <bits/stdc++.h>
using namespace std;
int n, S;
vector<string> board;
vector<vector<int>> vis;
vector<int> dx = {1, 0, -1, 0};
vector<int> dy = {0, 1, 0, -1};
struct point{
    int i, j;
};
void solve()
{
    n, S; cin >> n >> S;
    board = vector<string>(n);
    vis = vector<vector<int>> (n, vector<int> (n));
    for (int i = 0; i < n; ++i) cin >> board[i];
    point mecho, home;
    vector<point> honey;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] == 'H') honey.emplace_back(i, j);
            else if (board[i][j] == 'M') mecho = {i, j};
            else if (board[i][j] == 'D') home = {i, j};
        }
    }
    queue<point> mq;
    vector<vector<int>> dist(n, vector<int> (n, 0   ));
    for (auto x : honey) {
        mq.push(x);
        vis[x.i][x.j] = 1;
        dist[x.i][x.j] = 0;
    }
    while (!mq.empty()) {
        point u = mq.front();
        mq.pop();
        for (int i = 0; i < 4; ++i) {
            if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || vis[u.i+dx[i]][u.j+dy[i]] || board[u.i+dx[i]][u.j+dy[i]] == 'T') continue;
            mq.emplace(u.i + dx[i], u.j + dy[i]);
            vis[u.i + dx[i]][u.j + dy[i]] = 1;
            dist[u.i + dx[i]][u.j + dy[i]] = dist[u.i][u.j] + 1;
        }
    }
//    for (auto &x : dist)
//    {
//        for (auto y : x) cout << y << ' ';
//        cout << '\n';
//    }

    int l = -1, r = 1e9;
//    return;
    while (l + 1 < r) {
        vector<vector<int>> md(n, vector<int> (n));
        int m = (l + r) / 2;
        vis = vector<vector<int>> (n, vector<int> (n));
        queue<point> q;
        q.emplace(mecho.i, mecho.j);
        vis[mecho.i][mecho.j] = 1;
        if (m >= dist[mecho.i][mecho.j]) q.pop();
        while (!q.empty()) {
            point u = q.front();

            q.pop();
            for (int i = 0; i < 4; ++i) {
                int ni = u.i + dx[i], nj = u.j + dy[i];
                if (((md[u.i][u.j]+1) / S >= (dist[u.i][u.j] - m))) continue;
                if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || vis[u.i+dx[i]][u.j+dy[i]] || board[u.i+dx[i]][u.j+dy[i]] != 'G') continue;
                q.emplace(ni, nj);
                md[ni][nj] = md[u.i][u.j] + 1;
                vis[ni][nj] = 1;
            }
        }
        bool ok = false;
        for (int i = 0; i < 4; ++i) {
            point u = home;
            if (((md[u.i][u.j]+1) / S >= (dist[u.i][u.j] - m))) continue;
            if (u.i + dx[i] < 0 || u.i + dx[i] >= n || u.j + dy[i] < 0 || u.j + dy[i] >= n || board[u.i+dx[i]][u.j+dy[i]] != 'G') continue;
            if (vis[home.i + dx[i]][home.j+dy[i]]) ok = true;
        }
        if (ok) {
            l = m;
        } else r = m;
            
    }
    cout << l;

}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//#endif
    solve();
}

Compilation message

mecho.cpp: In function 'void solve()':
mecho.cpp:13:5: warning: left operand of comma operator has no effect [-Wunused-value]
   13 |     n, S; cin >> n >> S;
      |     ^
mecho.cpp:13:9: warning: right operand of comma operator has no effect [-Wunused-value]
   13 |     n, S; cin >> n >> S;
      |         ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from mecho.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = point; _Args = {int&, int&}; _Tp = point]':
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = point; _Args = {int&, int&}; _Tp = point; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<point>]'
/usr/include/c++/10/bits/vector.tcc:115:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&, int&}; _Tp = point; _Alloc = std::allocator<point>; std::vector<_Tp, _Alloc>::reference = point&]'
mecho.cpp:21:60:   required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
  150 |  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'point::point(int&)'
mecho.cpp:8:8: note: candidate: 'point::point()'
    8 | struct point{
      |        ^~~~~
mecho.cpp:8:8: note:   candidate expects 0 arguments, 1 provided
mecho.cpp:8:8: note: candidate: 'constexpr point::point(const point&)'
mecho.cpp:8:8: note:   no known conversion for argument 1 from 'int' to 'const point&'
mecho.cpp:8:8: note: candidate: 'constexpr point::point(point&&)'
mecho.cpp:8:8: note:   no known conversion for argument 1 from 'int' to 'point&&'
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/string:41,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from mecho.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = point; _Args = {int, int}; _Tp = point]':
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = point; _Args = {int, int}; _Tp = point; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<point>]'
/usr/include/c++/10/bits/deque.tcc:170:30:   required from 'std::deque<_Tp, _Alloc>::reference std::deque<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int, int}; _Tp = point; _Alloc = std::allocator<point>; std::deque<_Tp, _Alloc>::reference = point&]'
/usr/include/c++/10/bits/stl_queue.h:277:25:   required from 'decltype(auto) std::queue<_Tp, _Sequence>::emplace(_Args&& ...) [with _Args = {int, int}; _Tp = point; _Sequence = std::deque<point, std::allocator<point> >]'
mecho.cpp:38:48:   required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
  150 |  { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'point::point(int)'
mecho.cpp:8:8: note: candidate: 'point::point()'
    8 | struct point{
      |        ^~~~~
mecho.cpp:8:8: note:   candidate expects 0 arguments, 1 provided
mecho.cpp:8:8: note: candidate: 'constexpr point::point(const point&)'
mecho.cpp:8:8: note:   no known conversion for argument 1 from 'int' to 'const point&'
mecho.cpp:8:8: note: candidate: 'constexpr point::point(point&&)'
mecho.cpp:8:8: note:   no known conversion for argument 1 from 'int' to 'point&&'