제출 #491040

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491040		sberens	Mecho (IOI09_mecho)	C++17	4 / 100	14 ms	1100 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()) {
                cout << bees.size() + nextbees.size() << '\n';
                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();
            if (bees.empty()) break;
        }
        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, 0) - 1 << '\n';

}

• Subtask 1: 4 / 100