oj.uz

Submission #608803

# Submission time Handle Problem Language Result Execution time Memory
608803 2022-07-27T10:17:37 Z Mazaalai Mecho (IOI09_mecho) C++17
0 / 100
 5 ms 2904 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define LINE "---------------\n"
#define sz(a) (int)a.size()
using namespace std;
using PII = pair <int, int>;
const int N = 802;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n, m, X1, Y1, X2, Y2;
vector <PII> hives;
int mat[N][N], maze[N][N];
bool check(int lim) {
    memcpy(maze, mat, sizeof(mat));
    queue <PII> bfs1, bfs2;
    for (auto& [a, b] : hives) bfs2.push({a, b});
    for (int i = 0; i < lim; i++) {
        int rep = sz(bfs2);
        for (int j = 0; j < rep; j++) {
            int x, y; tie(x, y) = bfs2.front(); bfs2.pop();
            for (int a = 0; a < 4; a++) {
                int xx = dx[a] + x;
                int yy = dy[a] + y;
                if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] != 0) continue;
                maze[xx][yy] = 1;
                bfs2.push({xx, yy});
            }
        }
    }
    if (maze[X1][Y1] == 1) return 0;
    maze[X1][Y1] = 2;
    bfs1.push({X1, Y1});
    bool changed = 1;
    // cout << "START\n";
    // cout << lim << '\n';
    // for (int i = 1; i <= n; i++)
    // for (int j = 1; j <= n; j++) cout << maze[i][j] << " \n"[j==n];
            

    while (maze[X2][Y2] == 4 && changed) {
        // move bear
        changed = 0;
        for (int i = 0; i < m; i++) {
            int rep = sz(bfs1);
            for (int j = 0; j < rep; j++) {
                int x, y; tie(x, y) = bfs1.front(); bfs1.pop();
                if (maze[x][y] == 1) continue;
                for (int a = 0; a < 4; a++) {
                    int xx = dx[a] + x;
                    int yy = dy[a] + y;
                    if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] == 1 || maze[xx][yy] == 2) continue;
                    changed = 1;
                    maze[xx][yy] = 2;
                    bfs1.push({xx, yy});
                }
            }
        }
        if (maze[X2][Y2] != 4) return 1;
        // spread bees
        int rep = sz(bfs2);
        for (int j = 0; j < rep; j++) {
            int x, y; tie(x, y) = bfs2.front(); bfs2.pop();
            for (int a = 0; a < 4; a++) {
                int xx = dx[a] + x;
                int yy = dy[a] + y;
                if (xx < 1 || xx > n || yy < 1 || yy > n || maze[xx][yy] == 1 || maze[xx][yy] == 4) continue;

                changed = 1;
                maze[xx][yy] = 1;
                bfs2.push({xx, yy});
            }
        }
        // cout << LINE;
        // for (int i = 1; i <= n; i++)
        // for (int j = 1; j <= n; j++) cout << maze[i][j] << " \n"[j==n];
                
    }
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("0.in", "r", stdin);
    freopen("0.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
        char x; cin >> x;
        if (x == 'T') { // tree
            mat[i][j] = 1;
        } else if (x == 'G') { // grass
            mat[i][j] = 0;
        } else if (x == 'M') { // mecho the bear
            tie(X1, Y1) = mp(i, j);
            mat[i][j] = 0;
        } else if (x == 'D') { // home of the mecho
            mat[i][j] = 4;
            tie(X2, Y2) = mp(i, j);
        } else if (x == 'H') { // bee hive
            mat[i][j] = 1;
            hives.pb({i, j});
        }
    }
    int l = 0, r = n*n/2, ans = -1;
    while (l <= r) {
        int m = (l+r)>>1;
        if (check(m)) {
            l = m+1;
            ans = m;
        } else {
            r = m-1;
        }
    }
    cout << ans << "\n";
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     freopen("0.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
mecho.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     freopen("0.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2900 KB Output isn't correct
2 Incorrect 4 ms 2900 KB Output isn't correct
3 Incorrect 3 ms 2900 KB Output isn't correct
4 Incorrect 3 ms 2900 KB Output isn't correct
5 Incorrect 3 ms 2900 KB Output isn't correct
6 Incorrect 3 ms 2900 KB Output isn't correct
7 Incorrect 3 ms 2900 KB Output isn't correct
8 Incorrect 4 ms 2900 KB Output isn't correct
9 Incorrect 3 ms 2900 KB Output isn't correct
10 Incorrect 3 ms 2900 KB Output isn't correct
11 Incorrect 3 ms 2900 KB Output isn't correct
12 Incorrect 4 ms 2900 KB Output isn't correct
13 Incorrect 3 ms 2900 KB Output isn't correct
14 Incorrect 4 ms 2900 KB Output isn't correct
15 Incorrect 3 ms 2900 KB Output isn't correct
16 Incorrect 3 ms 2900 KB Output isn't correct
17 Incorrect 3 ms 2900 KB Output isn't correct
18 Incorrect 3 ms 2900 KB Output isn't correct
19 Incorrect 3 ms 2900 KB Output isn't correct
20 Incorrect 3 ms 2820 KB Output isn't correct
21 Incorrect 3 ms 2900 KB Output isn't correct
22 Incorrect 4 ms 2900 KB Output isn't correct
23 Incorrect 4 ms 2900 KB Output isn't correct
24 Incorrect 3 ms 2900 KB Output isn't correct
25 Incorrect 3 ms 2900 KB Output isn't correct
26 Incorrect 3 ms 2900 KB Output isn't correct
27 Incorrect 3 ms 2900 KB Output isn't correct
28 Incorrect 3 ms 2900 KB Output isn't correct
29 Incorrect 3 ms 2900 KB Output isn't correct
30 Incorrect 3 ms 2900 KB Output isn't correct
31 Incorrect 3 ms 2900 KB Output isn't correct
32 Incorrect 4 ms 2900 KB Output isn't correct
33 Incorrect 3 ms 2900 KB Output isn't correct
34 Incorrect 3 ms 2900 KB Output isn't correct
35 Incorrect 4 ms 2900 KB Output isn't correct
36 Incorrect 3 ms 2900 KB Output isn't correct
37 Incorrect 3 ms 2900 KB Output isn't correct
38 Incorrect 3 ms 2812 KB Output isn't correct
39 Incorrect 3 ms 2900 KB Output isn't correct
40 Incorrect 4 ms 2900 KB Output isn't correct
41 Incorrect 3 ms 2900 KB Output isn't correct
42 Incorrect 3 ms 2900 KB Output isn't correct
43 Incorrect 3 ms 2900 KB Output isn't correct
44 Incorrect 3 ms 2900 KB Output isn't correct
45 Incorrect 3 ms 2900 KB Output isn't correct
46 Incorrect 4 ms 2900 KB Output isn't correct
47 Incorrect 3 ms 2900 KB Output isn't correct
48 Incorrect 3 ms 2900 KB Output isn't correct
49 Incorrect 3 ms 2900 KB Output isn't correct
50 Incorrect 4 ms 2900 KB Output isn't correct
51 Incorrect 3 ms 2900 KB Output isn't correct
52 Incorrect 3 ms 2900 KB Output isn't correct
53 Incorrect 3 ms 2832 KB Output isn't correct
54 Incorrect 5 ms 2900 KB Output isn't correct
55 Incorrect 4 ms 2900 KB Output isn't correct
56 Incorrect 3 ms 2900 KB Output isn't correct
57 Incorrect 4 ms 2900 KB Output isn't correct
58 Incorrect 4 ms 2900 KB Output isn't correct
59 Incorrect 5 ms 2900 KB Output isn't correct
60 Incorrect 3 ms 2900 KB Output isn't correct
61 Incorrect 4 ms 2900 KB Output isn't correct
62 Incorrect 3 ms 2900 KB Output isn't correct
63 Incorrect 3 ms 2900 KB Output isn't correct
64 Incorrect 3 ms 2900 KB Output isn't correct
65 Incorrect 4 ms 2904 KB Output isn't correct
66 Incorrect 4 ms 2900 KB Output isn't correct
67 Incorrect 3 ms 2900 KB Output isn't correct
68 Incorrect 4 ms 2900 KB Output isn't correct
69 Incorrect 3 ms 2900 KB Output isn't correct
70 Incorrect 3 ms 2900 KB Output isn't correct
71 Incorrect 3 ms 2900 KB Output isn't correct
72 Incorrect 3 ms 2900 KB Output isn't correct
73 Incorrect 5 ms 2900 KB Output isn't correct
74 Incorrect 3 ms 2900 KB Output isn't correct
75 Incorrect 5 ms 2900 KB Output isn't correct
76 Incorrect 3 ms 2900 KB Output isn't correct
77 Incorrect 3 ms 2900 KB Output isn't correct
78 Incorrect 3 ms 2900 KB Output isn't correct
79 Incorrect 3 ms 2900 KB Output isn't correct
80 Incorrect 4 ms 2900 KB Output isn't correct
81 Incorrect 4 ms 2900 KB Output isn't correct
82 Incorrect 3 ms 2900 KB Output isn't correct
83 Incorrect 4 ms 2900 KB Output isn't correct
84 Incorrect 3 ms 2900 KB Output isn't correct
85 Incorrect 4 ms 2900 KB Output isn't correct
86 Incorrect 3 ms 2900 KB Output isn't correct
87 Incorrect 3 ms 2900 KB Output isn't correct
88 Incorrect 3 ms 2900 KB Output isn't correct
89 Incorrect 4 ms 2900 KB Output isn't correct
90 Incorrect 3 ms 2900 KB Output isn't correct
91 Incorrect 4 ms 2900 KB Output isn't correct
92 Incorrect 5 ms 2900 KB Output isn't correct