oj.uz

Submission #491043

# Submission time Handle Problem Language Result Execution time Memory
491043 2021-11-30T05:18:36 Z sberens Mecho (IOI09_mecho) C++17
0 / 100
 1000 ms 37212 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()) {
                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, n * n / 2) - 1 << '\n';

}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 Incorrect 1 ms 204 KB Output isn't correct
7 Execution timed out 1093 ms 33444 KB Time limit exceeded
8 Incorrect 1 ms 204 KB Output isn't correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Incorrect 1 ms 204 KB Output isn't correct
12 Incorrect 5 ms 332 KB Output isn't correct
13 Incorrect 4 ms 332 KB Output isn't correct
14 Incorrect 7 ms 460 KB Output isn't correct
15 Incorrect 1 ms 204 KB Output isn't correct
16 Incorrect 1 ms 204 KB Output isn't correct
17 Incorrect 1 ms 204 KB Output isn't correct
18 Incorrect 1 ms 332 KB Output isn't correct
19 Incorrect 1 ms 332 KB Output isn't correct
20 Incorrect 2 ms 204 KB Output isn't correct
21 Incorrect 2 ms 332 KB Output isn't correct
22 Incorrect 2 ms 332 KB Output isn't correct
23 Incorrect 3 ms 332 KB Output isn't correct
24 Incorrect 3 ms 272 KB Output isn't correct
25 Incorrect 4 ms 332 KB Output isn't correct
26 Incorrect 4 ms 332 KB Output isn't correct
27 Incorrect 6 ms 392 KB Output isn't correct
28 Incorrect 5 ms 332 KB Output isn't correct
29 Incorrect 6 ms 332 KB Output isn't correct
30 Incorrect 6 ms 332 KB Output isn't correct
31 Incorrect 8 ms 332 KB Output isn't correct
32 Incorrect 6 ms 332 KB Output isn't correct
33 Incorrect 218 ms 3204 KB Output isn't correct
34 Incorrect 249 ms 3248 KB Output isn't correct
35 Incorrect 196 ms 4092 KB Output isn't correct
36 Incorrect 299 ms 4200 KB Output isn't correct
37 Incorrect 278 ms 4208 KB Output isn't correct
38 Incorrect 297 ms 5612 KB Output isn't correct
39 Incorrect 397 ms 5364 KB Output isn't correct
40 Incorrect 336 ms 5080 KB Output isn't correct
41 Incorrect 351 ms 6904 KB Output isn't correct
42 Incorrect 487 ms 6556 KB Output isn't correct
43 Incorrect 418 ms 6492 KB Output isn't correct
44 Incorrect 458 ms 8816 KB Output isn't correct
45 Incorrect 566 ms 7792 KB Output isn't correct
46 Incorrect 516 ms 7732 KB Output isn't correct
47 Incorrect 547 ms 10652 KB Output isn't correct
48 Incorrect 672 ms 9820 KB Output isn't correct
49 Incorrect 652 ms 9600 KB Output isn't correct
50 Incorrect 610 ms 12696 KB Output isn't correct
51 Incorrect 820 ms 11420 KB Output isn't correct
52 Incorrect 791 ms 11332 KB Output isn't correct
53 Incorrect 804 ms 14992 KB Output isn't correct
54 Execution timed out 1030 ms 12956 KB Time limit exceeded
55 Incorrect 889 ms 12440 KB Output isn't correct
56 Incorrect 939 ms 17360 KB Output isn't correct
57 Execution timed out 1079 ms 14708 KB Time limit exceeded
58 Incorrect 991 ms 14844 KB Output isn't correct
59 Execution timed out 1031 ms 20060 KB Time limit exceeded
60 Execution timed out 1093 ms 15672 KB Time limit exceeded
61 Execution timed out 1088 ms 16016 KB Time limit exceeded
62 Execution timed out 1092 ms 23100 KB Time limit exceeded
63 Execution timed out 1066 ms 22140 KB Time limit exceeded
64 Execution timed out 1059 ms 17612 KB Time limit exceeded
65 Execution timed out 1092 ms 18464 KB Time limit exceeded
66 Execution timed out 1099 ms 21940 KB Time limit exceeded
67 Execution timed out 1096 ms 21924 KB Time limit exceeded
68 Execution timed out 1081 ms 29976 KB Time limit exceeded
69 Execution timed out 1076 ms 29172 KB Time limit exceeded
70 Execution timed out 1098 ms 30284 KB Time limit exceeded
71 Execution timed out 1094 ms 30236 KB Time limit exceeded
72 Execution timed out 1092 ms 30684 KB Time limit exceeded
73 Execution timed out 1087 ms 36012 KB Time limit exceeded
74 Execution timed out 1093 ms 36436 KB Time limit exceeded
75 Execution timed out 1086 ms 35536 KB Time limit exceeded
76 Execution timed out 1093 ms 36620 KB Time limit exceeded
77 Execution timed out 1090 ms 36336 KB Time limit exceeded
78 Execution timed out 1078 ms 34104 KB Time limit exceeded
79 Execution timed out 1085 ms 36852 KB Time limit exceeded
80 Execution timed out 1073 ms 36076 KB Time limit exceeded
81 Execution timed out 1093 ms 35476 KB Time limit exceeded
82 Execution timed out 1089 ms 36924 KB Time limit exceeded
83 Execution timed out 1088 ms 34580 KB Time limit exceeded
84 Execution timed out 1087 ms 36964 KB Time limit exceeded
85 Execution timed out 1085 ms 37212 KB Time limit exceeded
86 Execution timed out 1089 ms 36152 KB Time limit exceeded
87 Execution timed out 1089 ms 36352 KB Time limit exceeded
88 Execution timed out 1090 ms 37000 KB Time limit exceeded
89 Execution timed out 1091 ms 36852 KB Time limit exceeded
90 Execution timed out 1094 ms 34148 KB Time limit exceeded
91 Execution timed out 1046 ms 35048 KB Time limit exceeded
92 Execution timed out 1085 ms 35832 KB Time limit exceeded