Submission #491034

#	Time	Username	Problem	Language	Result	Execution time	Memory
491034		sberens	Mecho (IOI09_mecho)	C++17	0 / 100	13 ms	1364 KiB

mecho

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

const ll M = 1000000007;
const ll infll = M * M;

template<typename IN>
IN discrete_binary_search(function<bool(IN)> predicate, IN low = 0, IN high = numeric_limits<IN>::max()) {
    while (low < high) {
        IN middle = low + (high - low) / 2; // todo std::midpoint in cpp 2020
        if (predicate(middle))
            high = middle;
        else low = middle + 1;
    }
    return low;
}

vii dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

vii adjc(int x, int y) {
    vii res;
    for (auto [dx, dy] : dirs)
        res.pb({x + dx, y + dy});
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, s;
    cin >> n >> s;
    vv<char> g(n, vector<char>(n));
    int mr, mc, dr, dc;
    vii hives;
    F0R(i, n) {
        F0R(j, n) {
            char x;
            cin >> x;
            g[i][j] = x;
            if (x == 'M') {
                mr = i;
                mc = j;
            } else if (x == 'H') {
                hives.pb({i, j});
            } else if (x == 'D') {
                dr = i;
                dc = j;
            }
        }
    }
//    cout << discrete_binary_search<int>([&](int t) -> bool {
//        queue<ii> bees, bear;
//        vvi seenbees(n, vi(n)), seenbear(n, vi(n));
//        for (auto [r, c] : hives) {
//            bees.push({r, c});
//            seenbees[r][c] = 1;
//        }
//        bear.push({mr, mc});
//        seenbear[mr][mc] = 1;
//
//        auto upd_bees = [&]() -> void {
//            queue<ii> nextbees;
//            while (!bees.empty()) {
//                assert(bees.size() < n * n);
//                auto [r, c] = bees.front(); bees.pop();
//                for (auto [nr, nc] : adjc(r, c)) {
//                    if (0 <= nr && nr < n && 0 <= nc && nc < n && seenbees[nr][nc] == 0 && (g[nr][nc] == 'G' || g[nr][nc] == 'M')) {
//                        nextbees.push({nr, nc});
//                        seenbees[nr][nc] = 1;
//                    }
//                }
//            }
//            swap(bees, nextbees);
////            bees = nextbees;
//        };
//        F0R(_, t) upd_bees();
//        while (!bees.empty()) {
//            F0R(_, s) {
//                queue<ii> nextbear;
//                while (!bear.empty()) {
//                    assert(bear.size() < n * n);
//                    auto [r, c] = bear.front(); bear.pop();
//                    if (seenbees[r][c] == 1) continue;
//                    if (r == dr && c == dc) return false;
//                    for (auto [nr, nc] : adjc(r, c)) {
//                        if (0 <= nr && nr < n && 0 <= nc && nc < n && seenbear[nr][nc] == 0 && (g[nr][nc] == 'G' || g[nr][nc] == 'D') && seenbees[nr][nc] == 0) {
//                            nextbear.push({nr, nc});
//                            seenbear[nr][nc] = 1;
//                        }
//                    }
//                }
//                swap(bear, nextbear);
//                if (bear.empty()) return true;
////                bear = nextbear;
//            }
//            upd_bees();
//        }
//        return true;
//    }, 0, n * n) - 1 << '\n';

}

Compilation message (stderr)

mecho.cpp: In function 'int main()':
mecho.cpp:74:9: warning: variable 'mr' set but not used [-Wunused-but-set-variable]
   74 |     int mr, mc, dr, dc;
      |         ^~
mecho.cpp:74:13: warning: variable 'mc' set but not used [-Wunused-but-set-variable]
   74 |     int mr, mc, dr, dc;
      |             ^~
mecho.cpp:74:17: warning: variable 'dr' set but not used [-Wunused-but-set-variable]
   74 |     int mr, mc, dr, dc;
      |                 ^~
mecho.cpp:74:21: warning: variable 'dc' set but not used [-Wunused-but-set-variable]
   74 |     int mr, mc, dr, dc;
      |                     ^~

• Subtask 1: 0 / 100