oj.uz

Submission #491019

# Submission time Handle Problem Language Result Execution time Memory
491019 2021-11-30T04:26:23 Z sberens Mecho (IOI09_mecho) C++17
28 / 100
 1000 ms 7508 KB 
#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()) {
                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') {
                        nextbees.push({nr, nc});
                        seenbees[nr][nc] = 1;
                    }
                }
            }
            bees = nextbees;
        };
        F0R(_, t) upd_bees();
        while (!bees.empty()) {
            F0R(_, s) {
                queue<ii> nextbear;
                while (!bear.empty()) {
                    auto [r, c] = bear.front(); bear.pop();
                    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;
                        }
                    }
                }
                bear = nextbear;
            }
            upd_bees();
        }
        return true;
    }, 0, n * n) - 1 << '\n';

}

Subtask #1
28.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Execution timed out 1091 ms 6876 KB Time limit exceeded
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Incorrect 3 ms 332 KB Output isn't correct
13 Incorrect 3 ms 332 KB Output isn't correct
14 Correct 8 ms 332 KB Output is correct
15 Incorrect 1 ms 204 KB Output isn't correct
16 Correct 1 ms 204 KB Output is correct
17 Incorrect 1 ms 204 KB Output isn't correct
18 Correct 1 ms 204 KB Output is correct
19 Incorrect 1 ms 312 KB Output isn't correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 2 ms 332 KB Output isn't correct
22 Correct 2 ms 336 KB Output is correct
23 Incorrect 3 ms 332 KB Output isn't correct
24 Correct 3 ms 332 KB Output is correct
25 Incorrect 5 ms 332 KB Output isn't correct
26 Correct 5 ms 332 KB Output is correct
27 Incorrect 6 ms 368 KB Output isn't correct
28 Correct 7 ms 332 KB Output is correct
29 Incorrect 7 ms 372 KB Output isn't correct
30 Correct 8 ms 372 KB Output is correct
31 Incorrect 8 ms 332 KB Output isn't correct
32 Correct 11 ms 332 KB Output is correct
33 Incorrect 206 ms 1532 KB Output isn't correct
34 Correct 179 ms 1528 KB Output is correct
35 Correct 331 ms 1540 KB Output is correct
36 Incorrect 280 ms 1924 KB Output isn't correct
37 Correct 256 ms 1868 KB Output is correct
38 Correct 457 ms 2052 KB Output is correct
39 Incorrect 370 ms 2444 KB Output isn't correct
40 Correct 304 ms 2388 KB Output is correct
41 Correct 532 ms 2332 KB Output is correct
42 Incorrect 486 ms 2812 KB Output isn't correct
43 Correct 407 ms 2820 KB Output is correct
44 Correct 645 ms 2812 KB Output is correct
45 Incorrect 579 ms 3392 KB Output isn't correct
46 Correct 514 ms 3340 KB Output is correct
47 Correct 941 ms 3332 KB Output is correct
48 Incorrect 738 ms 3964 KB Output isn't correct
49 Correct 655 ms 3932 KB Output is correct
50 Correct 914 ms 3900 KB Output is correct
51 Incorrect 863 ms 4664 KB Output isn't correct
52 Correct 733 ms 4576 KB Output is correct
53 Execution timed out 1087 ms 4428 KB Time limit exceeded
54 Incorrect 993 ms 5216 KB Output isn't correct
55 Correct 764 ms 5196 KB Output is correct
56 Execution timed out 1096 ms 5196 KB Time limit exceeded
57 Execution timed out 1055 ms 6024 KB Time limit exceeded
58 Correct 895 ms 5980 KB Output is correct
59 Execution timed out 1075 ms 5920 KB Time limit exceeded
60 Execution timed out 1083 ms 6752 KB Time limit exceeded
61 Execution timed out 1043 ms 6688 KB Time limit exceeded
62 Execution timed out 1088 ms 6604 KB Time limit exceeded
63 Execution timed out 1091 ms 6768 KB Time limit exceeded
64 Execution timed out 1073 ms 6792 KB Time limit exceeded
65 Execution timed out 1097 ms 6664 KB Time limit exceeded
66 Execution timed out 1096 ms 6676 KB Time limit exceeded
67 Execution timed out 1094 ms 6604 KB Time limit exceeded
68 Execution timed out 1091 ms 6720 KB Time limit exceeded
69 Execution timed out 1050 ms 6732 KB Time limit exceeded
70 Execution timed out 1066 ms 6844 KB Time limit exceeded
71 Execution timed out 1042 ms 6728 KB Time limit exceeded
72 Execution timed out 1006 ms 6724 KB Time limit exceeded
73 Execution timed out 1091 ms 7244 KB Time limit exceeded
74 Execution timed out 1074 ms 7352 KB Time limit exceeded
75 Execution timed out 1098 ms 7276 KB Time limit exceeded
76 Execution timed out 1091 ms 7508 KB Time limit exceeded
77 Execution timed out 1089 ms 7384 KB Time limit exceeded
78 Execution timed out 1092 ms 7280 KB Time limit exceeded
79 Execution timed out 1099 ms 7164 KB Time limit exceeded
80 Execution timed out 1098 ms 7256 KB Time limit exceeded
81 Execution timed out 1091 ms 7224 KB Time limit exceeded
82 Execution timed out 1099 ms 7160 KB Time limit exceeded
83 Execution timed out 1098 ms 7140 KB Time limit exceeded
84 Execution timed out 1056 ms 7076 KB Time limit exceeded
85 Execution timed out 1056 ms 7216 KB Time limit exceeded
86 Execution timed out 1088 ms 7092 KB Time limit exceeded
87 Execution timed out 1088 ms 7104 KB Time limit exceeded
88 Execution timed out 1074 ms 7212 KB Time limit exceeded
89 Execution timed out 1090 ms 7020 KB Time limit exceeded
90 Execution timed out 1090 ms 6988 KB Time limit exceeded
91 Execution timed out 1094 ms 7224 KB Time limit exceeded
92 Execution timed out 1074 ms 7128 KB Time limit exceeded