Submission #953955

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

mecho

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <climits>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long

const ll MAXN = 810;
ll bee[MAXN][MAXN];
ll dist[MAXN][MAXN];
pair<ll,ll> parent[MAXN][MAXN];
bool vis[MAXN][MAXN];
ll dX[] = {1, -1, 0, 0};
ll dY[] = {0, 0, 1, -1};
pair<ll, ll> mencho, den;
vector<string> grid;
ll n, s;

bool compute(ll k){
    for (ll i = 0; i < MAXN; i++){
        for (ll j = 0; j < MAXN; j++){
            dist[i][j] = 1e9;
            parent[i][j] = {-1, -1};
            vis[i][j] = false;
        }
    }
    queue<pair<ll, ll>> q;
    q.push(mencho);
    dist[mencho.first][mencho.second] = 0;
    while (!q.empty()){
        ll x = q.front().first, y = q.front().second; q.pop();
        vis[x][y] = true;
        for (ll i = 0; i < 4; i++){
            ll nX = x + dX[i], nY = y+dY[i];
            if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'H'){
                continue;
            }
            if (dist[nX][nY] > dist[x][y]+1 && !vis[nX][nY]){
                dist[nX][nY] = dist[x][y]+1;
                parent[nX][nY] = {x, y};
                q.push({nX, nY});
            }
        }
    }
    pair<ll, ll> cur = parent[den.first][den.second];
    while (cur != make_pair(-1, -1)){
        if (k+(ll)(dist[cur.first][cur.second]+s-1)/s > bee[cur.first][cur.second]){
            return false;
        }
        cur = parent[cur.first][cur.second];
    }
    return true;
}

int main() {
    speedup
    cin >> n >> s;
    grid.resize(n);
    vector<pair<ll, ll>> start;
    for (ll i = 0; i < n; i++){
        string st; cin >> st;
        grid[i] = st;
        for (ll j = 0; j < n; j++){
            if (st[j] == 'H'){
                start.push_back({i, j});
            }else if (st[j] == 'M'){
                mencho = {i, j};
            }else if (st[j] == 'D'){
                den = {i, j};
            }
        }
    }
    for (ll i = 0; i < MAXN; i++){
        for (ll j = 0; j < MAXN; j++){
            bee[i][j] = 1e9;
            vis[i][j] = false;
        }
    }
    queue<pair<ll, ll>> q;
    for (pair<ll, ll> p: start){
        bee[p.first][p.second] = 0;
        q.push({p.first, p.second});
    }
    while (!q.empty()){
        ll x = q.front().first, y = q.front().second; q.pop();
        vis[x][y] = true;
        for (ll i = 0; i < 4; i++){
            ll nX = x + dX[i], nY = y+dY[i];
            if (nX < 0 || nX >= n || nY < 0 || nY >= n || grid[nX][nY] == 'T' || grid[nX][nY] == 'D'){
                continue;
            }
            if (bee[nX][nY] > bee[x][y]+1 && !vis[nX][nY]){
                bee[nX][nY] = bee[x][y]+1;
                q.push({nX, nY});
            }
        }
    }
    ll l = 0, h = 1e9, mid, ans = -1;
    while (l <= h){
        mid = (l+h)/2;
        if (compute(mid)){
            ans = mid;
            l = mid+1;
        }else{
            h = mid-1;
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

mecho.cpp: In function 'bool compute(long long int)':
mecho.cpp:53:16: error: no match for 'operator!=' (operand types are 'std::pair<long long int, long long int>' and 'std::pair<int, int>')
   53 |     while (cur != make_pair(-1, -1)){
      |            ~~~ ^~ ~~~~~~~~~~~~~~~~~
      |            |               |
      |            |               pair<int,int>
      |            pair<long long int,long long int>
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:1:
/usr/include/c++/10/bits/postypes.h:227:5: note: candidate: 'template<class _StateT> bool std::operator!=(const std::fpos<_StateT>&, const std::fpos<_StateT>&)'
  227 |     operator!=(const fpos<_StateT>& __lhs, const fpos<_StateT>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/postypes.h:227:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::fpos<_StateT>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:496:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator!=(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  496 |     operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:496:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   deduced conflicting types for parameter '_T1' ('long long int' and 'int')
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:372:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  372 |     operator!=(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:372:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:410:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  410 |     operator!=(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:410:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1444:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator!=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1444 |     operator!=(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1444:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::move_iterator<_IteratorL>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1501:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator!=(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1501 |     operator!=(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1501:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::move_iterator<_IteratorL>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/allocator.h:213:5: note: candidate: 'template<class _T1, class _T2> bool std::operator!=(const std::allocator<_CharT>&, const std::allocator<_T2>&)'
  213 |     operator!=(const allocator<_T1>&, const allocator<_T2>&)
      |     ^~~~~~~~
/usr/include/c++/10/bits/allocator.h:213:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::allocator<_CharT>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
                 from /usr/include/c++/10/string:55,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/string_view:525:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator!=(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
  525 |     operator!=(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:525:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
                 from /usr/include/c++/10/string:55,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/string_view:531:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator!=(std::basic_string_view<_CharT, _Traits>, std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >)'
  531 |     operator!=(basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:531:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
                 from /usr/include/c++/10/string:55,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/string_view:538:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator!=(std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >, std::basic_string_view<_CharT, _Traits>)'
  538 |     operator!=(__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:538:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<int, int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/string:55,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6229:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6229 |     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6229:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/string:55,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6242:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6242 |     operator!=(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6242:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   mismatched types 'const _CharT*' and 'std::pair<long long int, long long int>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/string:55,
                 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/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6254:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator!=(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
 6254 |     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6254:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/ios_base.h:46,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/system_error:398:3: note: candidate: 'bool std::operator!=(const std::error_code&, const std::error_code&)'
  398 |   operator!=(const error_code& __lhs, const error_code& __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/10/system_error:398:32: note:   no known conversion for argument 1 from 'std::pair<long long int, long long int>' to 'const std::error_code&'
  398 |   operator!=(const error_code& __lhs, const error_code& __rhs) noexcept
      |              ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/system_error:404:3: note: candidate: 'bool std::operator!=(const std::error_code&, const std::error_condition&)'
  404 |   operator!=(const error_code& __lhs, const error_condition& __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/10/system_error:404:32: note:   no known conversion for argument 1 from 'std::pair<long long int, long long int>' to 'const std::error_code&'
  404 |   operator!=(const error_code& __lhs, const error_condition& __rhs) noexcept
      |              ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/system_error:410:3: note: candidate: 'bool std::operator!=(const std::error_condition&, const std::error_code&)'
  410 |   operator!=(const error_condition& __lhs, const error_code& __rhs) noexcept
      |   ^~~~~~~~
/usr/include/c++/10/system_error:410:37: note:   no known conversion for argument 1 from 'std::pair<long long int, long long int>' to 'const std::error_condition&'
  410 |   operator!=(const error_condition& __lhs, const error_code& __rhs) noexcept
      |              ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/system_error:415:3: note: candidate: 'bool std::operator!=(const std::error_condition&, const std::error_condition&)'
  415 |   operator!=(const error_condition& __lhs,
      |   ^~~~~~~~
/usr/include/c++/10/system_error:415:37: note:   no known conversion for argument 1 from 'std::pair<long long int, long long int>' to 'const std::error_condition&'
  415 |   operator!=(const error_condition& __lhs,
      |              ~~~~~~~~~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/10/bits/locale_facets.h:48,
                 from /usr/include/c++/10/bits/basic_ios.h:37,
                 from /usr/include/c++/10/ios:44,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from mecho.cpp:1:
/usr/include/c++/10/bits/streambuf_iterator.h:233:5: note: candidate: 'template<class _CharT, class _Traits> bool std::operator!=(const std::istreambuf_iterator<_CharT, _Traits>&, const std::istreambuf_iterator<_CharT, _Traits>&)'
  233 |     operator!=(const istreambuf_iterator<_CharT, _Traits>& __a,
      |     ^~~~~~~~
/usr/include/c++/10/bits/streambuf_iterator.h:233:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::istreambuf_iterator<_CharT, _Traits>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/vector:67,
                 from mecho.cpp:2:
/usr/include/c++/10/bits/stl_vector.h:1937:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator!=(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&)'
 1937 |     operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1937:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::vector<_Tp, _Alloc>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/deque:67,
                 from /usr/include/c++/10/queue:60,
                 from mecho.cpp:3:
/usr/include/c++/10/bits/stl_deque.h:2286:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator!=(const std::deque<_Tp, _Alloc>&, const std::deque<_Tp, _Alloc>&)'
 2286 |     operator!=(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_deque.h:2286:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::deque<_Tp, _Alloc>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/queue:64,
                 from mecho.cpp:3:
/usr/include/c++/10/bits/stl_queue.h:368:5: note: candidate: 'template<class _Tp, class _Seq> bool std::operator!=(const std::queue<_Tp, _Seq>&, const std::queue<_Tp, _Seq>&)'
  368 |     operator!=(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_queue.h:368:5: note:   template argument deduction/substitution failed:
mecho.cpp:53:35: note:   'std::pair<long long int, long long int>' is not derived from 'const std::queue<_Tp, _Seq>'
   53 |     while (cur != make_pair(-1, -1)){
      |                                   ^
In file included from /usr/include/c++/10/bits/node_handle.h:39,
                 from /usr/include/c++/10/bits/stl_tree.h:72,
                 from /usr/include/c++/10/map:60,
                 from mecho.cpp:5:
/usr/include/c++/10/optional:994:5: note: candidate: 'template<class _Tp, class _Up