Submission #976010

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
976010	2024-05-06T04:59:06 Z	Br3ad	Mecho (IOI09_mecho)	C++17	46 / 100	13 ms	776 KB

mecho

#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;
        if(time_offset >= stepBee[ini.f][ini.s]) return false;

        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;
}

Subtask #1

46.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Runtime error	6 ms	604 KB	Execution killed with signal 11
8	Correct	0 ms	348 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	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 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	0 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	348 KB	Output is correct
21	Correct	4 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	600 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	344 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	344 KB	Output is correct
33	Incorrect	3 ms	348 KB	Output isn't correct
34	Runtime error	2 ms	604 KB	Execution killed with signal 11
35	Incorrect	4 ms	528 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	348 KB	Output isn't correct
39	Incorrect	2 ms	776 KB	Output isn't correct
40	Runtime error	3 ms	604 KB	Execution killed with signal 11
41	Incorrect	4 ms	348 KB	Output isn't correct
42	Incorrect	3 ms	344 KB	Output isn't correct
43	Runtime error	5 ms	600 KB	Execution killed with signal 11
44	Incorrect	5 ms	348 KB	Output isn't correct
45	Incorrect	4 ms	348 KB	Output isn't correct
46	Runtime error	6 ms	604 KB	Execution killed with signal 11
47	Incorrect	4 ms	528 KB	Output isn't correct
48	Runtime error	5 ms	612 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	604 KB	Execution killed with signal 11
52	Runtime error	5 ms	604 KB	Execution killed with signal 11
53	Runtime error	5 ms	600 KB	Execution killed with signal 11
54	Runtime error	5 ms	604 KB	Execution killed with signal 11
55	Runtime error	5 ms	604 KB	Execution killed with signal 11
56	Runtime error	5 ms	532 KB	Execution killed with signal 11
57	Runtime error	6 ms	532 KB	Execution killed with signal 11
58	Runtime error	8 ms	604 KB	Execution killed with signal 11
59	Runtime error	8 ms	532 KB	Execution killed with signal 11
60	Runtime error	7 ms	532 KB	Execution killed with signal 11
61	Runtime error	7 ms	556 KB	Execution killed with signal 11
62	Runtime error	8 ms	604 KB	Execution killed with signal 11
63	Runtime error	7 ms	604 KB	Execution killed with signal 11
64	Runtime error	7 ms	524 KB	Execution killed with signal 11
65	Runtime error	7 ms	604 KB	Execution killed with signal 11
66	Runtime error	6 ms	532 KB	Execution killed with signal 11
67	Runtime error	6 ms	604 KB	Execution killed with signal 11
68	Runtime error	7 ms	604 KB	Execution killed with signal 11
69	Runtime error	6 ms	604 KB	Execution killed with signal 11
70	Runtime error	7 ms	604 KB	Execution killed with signal 11
71	Runtime error	7 ms	528 KB	Execution killed with signal 11
72	Runtime error	7 ms	604 KB	Execution killed with signal 11
73	Incorrect	6 ms	344 KB	Output isn't correct
74	Incorrect	9 ms	348 KB	Output isn't correct
75	Incorrect	9 ms	348 KB	Output isn't correct
76	Incorrect	8 ms	348 KB	Output isn't correct
77	Incorrect	13 ms	344 KB	Output isn't correct
78	Runtime error	10 ms	604 KB	Execution killed with signal 11
79	Runtime error	7 ms	604 KB	Execution killed with signal 11
80	Runtime error	8 ms	528 KB	Execution killed with signal 11
81	Runtime error	7 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	604 KB	Execution killed with signal 11
84	Runtime error	10 ms	604 KB	Execution killed with signal 11
85	Runtime error	7 ms	604 KB	Execution killed with signal 11
86	Runtime error	7 ms	604 KB	Execution killed with signal 11
87	Runtime error	7 ms	532 KB	Execution killed with signal 11
88	Runtime error	6 ms	604 KB	Execution killed with signal 11
89	Runtime error	6 ms	604 KB	Execution killed with signal 11
90	Runtime error	6 ms	604 KB	Execution killed with signal 11
91	Runtime error	7 ms	532 KB	Execution killed with signal 11
92	Runtime error	6 ms	528 KB	Execution killed with signal 11