Submission #975995

# Submission time Handle Problem Language Result Execution time Memory
975995 2024-05-06T04:50:29 Z Br3ad Mecho (IOI09_mecho) C++17
38 / 100
10 ms 856 KB
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 8e1 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

const int xMove[4] = {0, 1, 0, -1};
const int yMove[4] = {1, 0, -1, 0};

int bin(int l, int r, function<bool(int)> f){
    while(l < r){
        int mid = l + (r - l + 1)/2;
        if(f(mid)){
            l = mid;
        }else {
            r = mid - 1;
        }
    }
    return r;
}

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // ifstream cin();
    // ofstream cout();
    
    pair<int, int> ini;
    char c[N][N];
    int n, step;
    cin >> n >> step;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> c[i][j];
            if(c[i][j] == 'M') ini = MP(i, j);
        }
    }

    queue<pair<int, int>> bee;
    bool vis_bee[N][N]{false};
    int stepBee[N][N]{0};
    memset(stepBee, inf, sizeof(stepBee));

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(c[i][j] == 'H'){
                bee.push(MP(i, j));
                vis_bee[i][j] = true;
                stepBee[i][j] = 0;
            }
        }
    }

    while(!bee.empty()){
        auto [x, y] = bee.front();
        bee.pop();

        for(int i = 0; i < 4; i++){
            int new_x = x + xMove[i];
            int new_y = y + yMove[i];
            if(new_x < 0 || new_x >= n || new_y < 0 || new_y >= n) continue;
            if(c[new_x][new_y] == 'T' || c[new_x][new_y] == 'D') continue;
            if(vis_bee[new_x][new_y]) continue;

            vis_bee[new_x][new_y] = true;
            stepBee[new_x][new_y] = stepBee[x][y] + 1;
            bee.push(MP(new_x, new_y));
        }
    }
    
    bool vis_bear[N][N]{false};
    int stepBear[N][N]{0};
    int ans = bin(-1, N*N, [&](int time_offset){
        // Initialize
        memset(vis_bear, false, sizeof(vis_bear));
        memset(stepBear, 0, sizeof(stepBear));

        queue<pair<int, int>> bear;
        bear.push(ini);
        vis_bear[ini.f][ini.s] = true;

        while(!bear.empty()){
            auto [x, y] = bear.front();
            bear.pop();

            if(c[x][y] == 'D') return true;

            int cur_time = (stepBear[x][y] + 1)/step + time_offset;

            for(int i = 0; i < 4; i++){
                int new_x = x + xMove[i];
                int new_y = y + yMove[i];
                if(new_x < 0 || new_x >= n || new_y < 0 || new_y >= n) continue;
                if(c[new_x][new_y] == 'T' || vis_bear[new_x][new_y]) continue;
                if(cur_time >= stepBee[new_x][new_y]) continue;

                vis_bear[new_x][new_y] = true;
                stepBear[new_x][new_y] = stepBear[x][y] + 1;

                bear.push(MP(new_x, new_y));
            }
        }

        return false;
    });

    cout << ans << endl;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Runtime error 7 ms 528 KB Execution killed with signal 11
8 Correct 1 ms 428 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Incorrect 1 ms 348 KB Output isn't correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 512 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Incorrect 2 ms 348 KB Output isn't correct
34 Runtime error 2 ms 604 KB Execution killed with signal 11
35 Incorrect 2 ms 348 KB Output isn't correct
36 Incorrect 2 ms 348 KB Output isn't correct
37 Runtime error 2 ms 604 KB Execution killed with signal 11
38 Incorrect 3 ms 344 KB Output isn't correct
39 Incorrect 2 ms 348 KB Output isn't correct
40 Runtime error 2 ms 604 KB Execution killed with signal 11
41 Incorrect 4 ms 348 KB Output isn't correct
42 Incorrect 3 ms 348 KB Output isn't correct
43 Runtime error 3 ms 604 KB Execution killed with signal 11
44 Incorrect 3 ms 348 KB Output isn't correct
45 Incorrect 3 ms 532 KB Output isn't correct
46 Runtime error 3 ms 604 KB Execution killed with signal 11
47 Incorrect 4 ms 524 KB Output isn't correct
48 Runtime error 4 ms 604 KB Execution killed with signal 11
49 Runtime error 4 ms 604 KB Execution killed with signal 11
50 Runtime error 4 ms 604 KB Execution killed with signal 11
51 Runtime error 5 ms 528 KB Execution killed with signal 11
52 Runtime error 4 ms 604 KB Execution killed with signal 11
53 Runtime error 5 ms 528 KB Execution killed with signal 11
54 Runtime error 6 ms 600 KB Execution killed with signal 11
55 Runtime error 5 ms 600 KB Execution killed with signal 11
56 Runtime error 5 ms 604 KB Execution killed with signal 11
57 Runtime error 6 ms 604 KB Execution killed with signal 11
58 Runtime error 9 ms 532 KB Execution killed with signal 11
59 Runtime error 6 ms 600 KB Execution killed with signal 11
60 Runtime error 7 ms 600 KB Execution killed with signal 11
61 Runtime error 7 ms 604 KB Execution killed with signal 11
62 Runtime error 7 ms 528 KB Execution killed with signal 11
63 Runtime error 6 ms 604 KB Execution killed with signal 11
64 Runtime error 6 ms 604 KB Execution killed with signal 11
65 Runtime error 6 ms 528 KB Execution killed with signal 11
66 Runtime error 6 ms 604 KB Execution killed with signal 11
67 Runtime error 7 ms 604 KB Execution killed with signal 11
68 Runtime error 6 ms 604 KB Execution killed with signal 11
69 Runtime error 6 ms 528 KB Execution killed with signal 11
70 Runtime error 7 ms 600 KB Execution killed with signal 11
71 Runtime error 6 ms 604 KB Execution killed with signal 11
72 Runtime error 6 ms 604 KB Execution killed with signal 11
73 Incorrect 6 ms 348 KB Output isn't correct
74 Incorrect 8 ms 348 KB Output isn't correct
75 Incorrect 10 ms 528 KB Output isn't correct
76 Incorrect 8 ms 344 KB Output isn't correct
77 Incorrect 7 ms 528 KB Output isn't correct
78 Runtime error 6 ms 604 KB Execution killed with signal 11
79 Runtime error 6 ms 604 KB Execution killed with signal 11
80 Runtime error 6 ms 604 KB Execution killed with signal 11
81 Runtime error 6 ms 604 KB Execution killed with signal 11
82 Runtime error 6 ms 604 KB Execution killed with signal 11
83 Runtime error 6 ms 528 KB Execution killed with signal 11
84 Runtime error 7 ms 604 KB Execution killed with signal 11
85 Runtime error 6 ms 600 KB Execution killed with signal 11
86 Runtime error 6 ms 604 KB Execution killed with signal 11
87 Runtime error 6 ms 604 KB Execution killed with signal 11
88 Runtime error 6 ms 604 KB Execution killed with signal 11
89 Runtime error 6 ms 856 KB Execution killed with signal 11
90 Runtime error 8 ms 536 KB Execution killed with signal 11
91 Runtime error 6 ms 604 KB Execution killed with signal 11
92 Runtime error 6 ms 604 KB Execution killed with signal 11