Submission #803124

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
803124	2023-08-02T22:44:00 Z	Liudas	Mecho (IOI09_mecho)	C++17	10 / 100	237 ms	10844 KB

mecho

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N, S;
    cin >> N >> S;
    vector<string> _map(N + 2);
    string t = string('T', N + 2);
    _map[0] = t;
    _map[N+1] = t;
    for(int i = 1; i <= N; i ++){
        cin >> _map[i];
        _map[i] = "T"+_map[i] + "T";
    }
    int sx, sy, ex, ey;
    vector<pair<int, int>> bees;
    for(int i = 1; i <= N;  i++){
        for(int j = 1; j <= N; j ++){
            if(_map[i][j] == 'M'){
                sx = j;
                sy = i;
                _map[i][j]='G';
            }
            if(_map[i][j] == 'D'){
                ex = j;
                ey = i;
            }
            if(_map[i][j] == 'H'){
                _map[i][j] == 'T';
                bees.push_back({i, j});
            }
        }
    }
    vector<int> dx = {1,-1,0,0}, dy = {0,0,1,-1};
    int l = 0, r = N * N + 10;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        //cout << mid << " " << l << " " << r << endl;
        vector<string> arr = _map;
        vector<vector<int>> been(N + 2, vector<int>(N + 2));
        queue<pair<int, int>> bee, bee2, moves;
        moves.push({sy, sx});
        for(auto[l, r] : bees){
            bee.push({l, r});
        }
        bool reach = false;
        for(int j = 0; j < mid; j ++){
            while(!bee.empty()){
                int a = bee.front().first, b = bee.front().second;
                bee.pop();
                for(int i = 0; i < 4; i ++){
                    if(arr[a+dy[i]][b+dx[i]] == 'G'){
                        arr[a+dy[i]][b+dx[i]] = 'T';
                        bee2.push({a+dy[i], b+dx[i]});
                    }
                }
            }
            swap(bee, bee2);
        }
        int it = 0;
        while(!moves.empty() && !reach){
            while(!moves.empty()){
                int a = moves.front().first, b = moves.front().second;
                //cout << a << " " << b << " " << mid << endl;
                if(been[a][b] > (it + 1) * S)break;
                if(arr[a][b]=='D'){reach = true;break;}
                moves.pop();
                //cout << arr[a][b] << endl;
                if(arr[a][b] == 'T')continue;
                for(int i = 0; i < 4; i ++){
                   // cout << a + dy[i] << " " << endl;
                    if(!been[a+dy[i]][b+dx[i]] && arr[a+dy[i]][b+dx[i]] != 'T'){
                        been[a+dy[i]][b+dx[i]] = been[a][b] + 1;
                        moves.push({a+dy[i], b+dx[i]});
                    }
                }
            }
            //cout << " ?" << endl;
            while(!bee.empty()){
                int a = bee.front().first, b = bee.front().second;
                bee.pop();
                for(int i = 0; i < 4; i ++){
                    if(arr[a+dy[i]][b+dx[i]] == 'G'){
                        arr[a+dy[i]][b+dx[i]] = 'T';
                        bee2.push({a+dy[i], b+dx[i]});
                    }
                }
            }
            swap(bee, bee2);
            it++;
        }
        if(reach){
            l = mid;
        }
        else{
            r = mid;
        }
    }
    cout << l << endl;
    return 0;
}

Compilation message

mecho.cpp: In function 'int main()':
mecho.cpp:31:28: warning: value computed is not used [-Wunused-value]
   31 |                 _map[i][j] == 'T';
mecho.cpp:17:17: warning: variable 'ex' set but not used [-Wunused-but-set-variable]
   17 |     int sx, sy, ex, ey;
      |                 ^~
mecho.cpp:17:21: warning: variable 'ey' set but not used [-Wunused-but-set-variable]
   17 |     int sx, sy, ex, ey;
      |                     ^~

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	340 KB	Execution killed with signal 11
2	Runtime error	1 ms	340 KB	Execution killed with signal 11
3	Runtime error	1 ms	340 KB	Execution killed with signal 11
4	Runtime error	1 ms	432 KB	Execution killed with signal 11
5	Correct	0 ms	212 KB	Output is correct
6	Runtime error	1 ms	340 KB	Execution killed with signal 11
7	Runtime error	23 ms	10352 KB	Execution killed with signal 11
8	Runtime error	1 ms	340 KB	Execution killed with signal 11
9	Runtime error	1 ms	340 KB	Execution killed with signal 11
10	Runtime error	1 ms	340 KB	Execution killed with signal 11
11	Runtime error	1 ms	428 KB	Execution killed with signal 11
12	Correct	1 ms	300 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Incorrect	1 ms	340 KB	Output isn't correct
15	Runtime error	1 ms	428 KB	Execution killed with signal 11
16	Runtime error	1 ms	428 KB	Execution killed with signal 11
17	Runtime error	1 ms	340 KB	Execution killed with signal 11
18	Runtime error	1 ms	340 KB	Execution killed with signal 11
19	Runtime error	1 ms	468 KB	Execution killed with signal 11
20	Runtime error	1 ms	424 KB	Execution killed with signal 11
21	Runtime error	1 ms	428 KB	Execution killed with signal 11
22	Runtime error	1 ms	340 KB	Execution killed with signal 11
23	Runtime error	1 ms	468 KB	Execution killed with signal 11
24	Runtime error	1 ms	468 KB	Execution killed with signal 11
25	Runtime error	1 ms	424 KB	Execution killed with signal 11
26	Runtime error	1 ms	468 KB	Execution killed with signal 11
27	Runtime error	1 ms	468 KB	Execution killed with signal 11
28	Runtime error	1 ms	468 KB	Execution killed with signal 11
29	Runtime error	1 ms	468 KB	Execution killed with signal 11
30	Runtime error	1 ms	468 KB	Execution killed with signal 11
31	Runtime error	1 ms	468 KB	Execution killed with signal 11
32	Runtime error	1 ms	468 KB	Execution killed with signal 11
33	Runtime error	6 ms	2260 KB	Execution killed with signal 11
34	Runtime error	4 ms	2260 KB	Execution killed with signal 11
35	Runtime error	4 ms	2260 KB	Execution killed with signal 11
36	Runtime error	7 ms	2896 KB	Execution killed with signal 11
37	Runtime error	5 ms	2880 KB	Execution killed with signal 11
38	Runtime error	7 ms	2876 KB	Execution killed with signal 11
39	Runtime error	8 ms	3540 KB	Execution killed with signal 11
40	Runtime error	5 ms	3540 KB	Execution killed with signal 11
41	Runtime error	13 ms	3636 KB	Execution killed with signal 11
42	Runtime error	9 ms	4180 KB	Execution killed with signal 11
43	Runtime error	6 ms	4180 KB	Execution killed with signal 11
44	Runtime error	16 ms	4264 KB	Execution killed with signal 11
45	Runtime error	10 ms	5076 KB	Execution killed with signal 11
46	Runtime error	8 ms	5048 KB	Execution killed with signal 11
47	Runtime error	8 ms	4976 KB	Execution killed with signal 11
48	Runtime error	13 ms	5920 KB	Execution killed with signal 11
49	Runtime error	15 ms	5844 KB	Execution killed with signal 11
50	Runtime error	9 ms	5932 KB	Execution killed with signal 11
51	Runtime error	16 ms	6832 KB	Execution killed with signal 11
52	Runtime error	11 ms	6844 KB	Execution killed with signal 11
53	Runtime error	20 ms	6916 KB	Execution killed with signal 11
54	Runtime error	21 ms	7824 KB	Execution killed with signal 11
55	Runtime error	14 ms	7892 KB	Execution killed with signal 11
56	Runtime error	65 ms	7832 KB	Execution killed with signal 11
57	Runtime error	21 ms	8980 KB	Execution killed with signal 11
58	Runtime error	18 ms	9004 KB	Execution killed with signal 11
59	Runtime error	15 ms	8928 KB	Execution killed with signal 11
60	Runtime error	24 ms	10092 KB	Execution killed with signal 11
61	Runtime error	15 ms	10100 KB	Execution killed with signal 11
62	Runtime error	31 ms	10156 KB	Execution killed with signal 11
63	Runtime error	16 ms	10088 KB	Execution killed with signal 11
64	Runtime error	16 ms	10104 KB	Execution killed with signal 11
65	Runtime error	18 ms	10116 KB	Execution killed with signal 11
66	Runtime error	15 ms	10068 KB	Execution killed with signal 11
67	Runtime error	21 ms	10068 KB	Execution killed with signal 11
68	Runtime error	17 ms	10100 KB	Execution killed with signal 11
69	Runtime error	15 ms	10196 KB	Execution killed with signal 11
70	Runtime error	19 ms	10128 KB	Execution killed with signal 11
71	Runtime error	16 ms	10060 KB	Execution killed with signal 11
72	Runtime error	15 ms	10196 KB	Execution killed with signal 11
73	Correct	167 ms	5716 KB	Output is correct
74	Runtime error	16 ms	10324 KB	Execution killed with signal 11
75	Runtime error	132 ms	10716 KB	Execution killed with signal 11
76	Runtime error	174 ms	10844 KB	Execution killed with signal 11
77	Runtime error	134 ms	10696 KB	Execution killed with signal 11
78	Incorrect	197 ms	5692 KB	Output isn't correct
79	Correct	195 ms	5716 KB	Output is correct
80	Correct	200 ms	5712 KB	Output is correct
81	Correct	196 ms	5656 KB	Output is correct
82	Correct	194 ms	5692 KB	Output is correct
83	Runtime error	28 ms	10648 KB	Execution killed with signal 11
84	Correct	223 ms	5652 KB	Output is correct
85	Correct	210 ms	5652 KB	Output is correct
86	Runtime error	27 ms	10572 KB	Execution killed with signal 11
87	Correct	228 ms	5748 KB	Output is correct
88	Runtime error	116 ms	10472 KB	Execution killed with signal 11
89	Correct	235 ms	5580 KB	Output is correct
90	Correct	218 ms	5592 KB	Output is correct
91	Correct	193 ms	5592 KB	Output is correct
92	Correct	237 ms	5592 KB	Output is correct