oj.uz

Submission #482593

# Submission time Handle Problem Language Result Execution time Memory
482593 2021-10-25T18:09:44 Z danielsuh Mecho (IOI09_mecho) C++17
7 / 100
 1000 ms 65540 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int mxN = 805;
int N, S; 
char grid[mxN][mxN], store_grid[mxN][mxN];
int dist[mxN][mxN];
pair<int, int> start, finish;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
 
bool check(int seconds) {
    // Can you just simulate the first w seconds and then find the BFS thing?
    for(auto &x : dist) for(auto &y : x) y = INT_MAX;
    for(int i = 0; i < N; i++) 
        for(int j = 0; j < N; j++)
            grid[i][j] = store_grid[i][j];
    
    bool reached_end = 0;
    for(int i = 0; i < seconds; i++) {
        vector<pair<int, int>> change;
        for(int j = 0; j < N; j++) {
            for(int k = 0; k < N; k++) {
                if(grid[j][k] == 'H') {
                    for(int it = 0; it < 4; it++) {
                        if(j - 1 >= 0 && grid[j - 1][k] != 'M' && grid[j - 1][k] != 'D' && grid[j - 1][k] != 'T') change.push_back(make_pair(j - 1, k));
                        if(j + 1 < N && grid[j + 1][k] != 'M' && grid[j + 1][k] != 'D' && grid[j + 1][k] != 'T') change.push_back(make_pair(j + 1, k));
                        if(k - 1 >= 0 && grid[j][k - 1] != 'M' && grid[j][k - 1] != 'D' && grid[j][k - 1] != 'T') change.push_back(make_pair(j, k - 1));
                        if(k + 1 < N && grid[j][k + 1] != 'M' && grid[j][k + 1] != 'D' && grid[j][k + 1] != 'T') change.push_back(make_pair(j, k + 1));
                    }
                }
            }
        }
        for(auto &x : change) grid[x.first][x.second] = 'H';
    }
    queue<pair<pair<int, int>, int>> q;
    q.push({make_pair(start.first, start.second), 0});
    dist[start.first][start.second] = 0;
    unordered_map<int, bool> considered;
    while(!q.empty()) {
        if(q.front().second % S == 0 && q.front().second != 0 && !considered[q.front().second]) {
            vector<pair<int, int>> change;
            for(int j = 0; j < N; j++) {
                for(int k = 0; k < N; k++) {
                    if(grid[j][k] == 'H') {
                        for(int it = 0; it < 4; it++) {
                            if(j - 1 >= 0 && grid[j - 1][k] != 'M' && grid[j - 1][k] != 'D' && grid[j - 1][k] != 'T') change.push_back(make_pair(j - 1, k));
                            if(j + 1 < N && grid[j + 1][k] != 'M' && grid[j + 1][k] != 'D' && grid[j + 1][k] != 'T') change.push_back(make_pair(j + 1, k));
                            if(k - 1 >= 0 && grid[j][k - 1] != 'M' && grid[j][k - 1] != 'D' && grid[j][k - 1] != 'T') change.push_back(make_pair(j, k - 1));
                            if(k + 1 < N && grid[j][k + 1] != 'M' && grid[j][k + 1] != 'D' && grid[j][k + 1] != 'T') change.push_back(make_pair(j, k + 1));
                        }
                    }
                }
            }
            for(auto &x : change) grid[x.first][x.second] = 'H';
            considered[q.front().second] = true;
            continue;
        }
        int x = q.front().first.first, y = q.front().first.second; 
        int cur_second = q.front().second;
        q.pop();
        if(grid[x][y] == 'H' || grid[x][y] == 'T') continue;
        if(grid[x][y] == 'D') return true;
        for(int i = 0; i < 4; i++) {
            if(x + dx[i] > 0 && y + dy[i] > 0 && x + dx[i] < N && y + dy[i] < N && dist[x][y] + 1 < dist[x + dx[i]][y + dy[i]]) {
                q.push({make_pair(x + dx[i], y + dy[i]), cur_second + 1});
                dist[x + dx[i]][y + dy[i]] = dist[x][y] + 1;
            }
        }
    }
    return false;
}
 
int bin_search() {
    int lo = 0, hi = N * N;
    while(lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if(check(mid)) {
            lo = mid;
        }else {
            hi = mid - 1;
        }
    }
    return lo;
}
 
void solve() {
    cin >> N >> S;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> grid[i][j];
            store_grid[i][j] = grid[i][j];
            if(grid[i][j] == 'M') {
                start.first = i, start.second = j;
            }else if(grid[i][j] == 'D') {
                finish.first = i, finish.second = j;
            }
       }
    }
    cout << bin_search() << "\n";
}
 
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for(int i = 1; i <= T; ++i) {
        solve();
    }
}

Compilation message

mecho.cpp: In function 'bool check(int)':
mecho.cpp:21:10: warning: unused variable 'reached_end' [-Wunused-variable]
   21 |     bool reached_end = 0;
      |          ^~~~~~~~~~~

Subtask #1
7.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2764 KB Output isn't correct
2 Incorrect 2 ms 2772 KB Output isn't correct
3 Incorrect 2 ms 2764 KB Output isn't correct
4 Incorrect 3 ms 2764 KB Output isn't correct
5 Correct 3 ms 2764 KB Output is correct
6 Incorrect 5 ms 2892 KB Output isn't correct
7 Execution timed out 1063 ms 65540 KB Time limit exceeded
8 Incorrect 12 ms 2892 KB Output isn't correct
9 Correct 12 ms 2960 KB Output is correct
10 Correct 12 ms 2932 KB Output is correct
11 Correct 13 ms 2932 KB Output is correct
12 Incorrect 722 ms 3360 KB Output isn't correct
13 Execution timed out 1092 ms 3540 KB Time limit exceeded
14 Execution timed out 1052 ms 3996 KB Time limit exceeded
15 Incorrect 7 ms 2892 KB Output isn't correct
16 Correct 14 ms 2892 KB Output is correct
17 Incorrect 14 ms 2944 KB Output isn't correct
18 Correct 28 ms 2936 KB Output is correct
19 Incorrect 20 ms 2968 KB Output isn't correct
20 Correct 53 ms 2892 KB Output is correct
21 Incorrect 53 ms 2980 KB Output isn't correct
22 Correct 189 ms 3020 KB Output is correct
23 Incorrect 128 ms 3780 KB Output isn't correct
24 Correct 490 ms 3296 KB Output is correct
25 Incorrect 270 ms 3164 KB Output isn't correct
26 Execution timed out 1093 ms 3288 KB Time limit exceeded
27 Incorrect 405 ms 3340 KB Output isn't correct
28 Execution timed out 1087 ms 3380 KB Time limit exceeded
29 Incorrect 562 ms 3428 KB Output isn't correct
30 Execution timed out 1086 ms 3436 KB Time limit exceeded
31 Incorrect 721 ms 3692 KB Output isn't correct
32 Execution timed out 1090 ms 3436 KB Time limit exceeded
33 Execution timed out 1078 ms 3976 KB Time limit exceeded
34 Execution timed out 1093 ms 4180 KB Time limit exceeded
35 Execution timed out 1082 ms 16216 KB Time limit exceeded
36 Execution timed out 1098 ms 3904 KB Time limit exceeded
37 Execution timed out 1094 ms 4276 KB Time limit exceeded
38 Execution timed out 1093 ms 16688 KB Time limit exceeded
39 Execution timed out 1100 ms 3972 KB Time limit exceeded
40 Execution timed out 1097 ms 4404 KB Time limit exceeded
41 Execution timed out 1100 ms 16984 KB Time limit exceeded
42 Execution timed out 1090 ms 4088 KB Time limit exceeded
43 Execution timed out 1092 ms 4432 KB Time limit exceeded
44 Execution timed out 1096 ms 17136 KB Time limit exceeded
45 Execution timed out 1091 ms 4308 KB Time limit exceeded
46 Execution timed out 1093 ms 4212 KB Time limit exceeded
47 Execution timed out 1092 ms 17184 KB Time limit exceeded
48 Execution timed out 1091 ms 4340 KB Time limit exceeded
49 Execution timed out 1096 ms 4540 KB Time limit exceeded
50 Execution timed out 1081 ms 17112 KB Time limit exceeded
51 Execution timed out 1097 ms 4108 KB Time limit exceeded
52 Execution timed out 1098 ms 4356 KB Time limit exceeded
53 Execution timed out 1089 ms 17176 KB Time limit exceeded
54 Execution timed out 1059 ms 4284 KB Time limit exceeded
55 Execution timed out 1081 ms 4708 KB Time limit exceeded
56 Execution timed out 1079 ms 17108 KB Time limit exceeded
57 Execution timed out 1087 ms 4244 KB Time limit exceeded
58 Execution timed out 1089 ms 4540 KB Time limit exceeded
59 Execution timed out 1092 ms 17240 KB Time limit exceeded
60 Execution timed out 1083 ms 4320 KB Time limit exceeded
61 Execution timed out 1098 ms 4816 KB Time limit exceeded
62 Execution timed out 1097 ms 17292 KB Time limit exceeded
63 Execution timed out 1094 ms 8236 KB Time limit exceeded
64 Execution timed out 1097 ms 7620 KB Time limit exceeded
65 Execution timed out 1090 ms 7684 KB Time limit exceeded
66 Execution timed out 1087 ms 8144 KB Time limit exceeded
67 Execution timed out 1093 ms 8332 KB Time limit exceeded
68 Execution timed out 1099 ms 33052 KB Time limit exceeded
69 Execution timed out 1099 ms 33092 KB Time limit exceeded
70 Execution timed out 1073 ms 32900 KB Time limit exceeded
71 Execution timed out 1058 ms 32716 KB Time limit exceeded
72 Execution timed out 1089 ms 32760 KB Time limit exceeded
73 Runtime error 521 ms 65540 KB Execution killed with signal 9
74 Runtime error 528 ms 65540 KB Execution killed with signal 9
75 Runtime error 588 ms 65540 KB Execution killed with signal 9
76 Runtime error 565 ms 65540 KB Execution killed with signal 9
77 Runtime error 540 ms 65540 KB Execution killed with signal 9
78 Runtime error 553 ms 65540 KB Execution killed with signal 9
79 Runtime error 563 ms 65540 KB Execution killed with signal 9
80 Runtime error 606 ms 65540 KB Execution killed with signal 9
81 Runtime error 563 ms 65540 KB Execution killed with signal 9
82 Runtime error 566 ms 65540 KB Execution killed with signal 9
83 Runtime error 613 ms 65540 KB Execution killed with signal 9
84 Runtime error 607 ms 65540 KB Execution killed with signal 9
85 Runtime error 621 ms 65540 KB Execution killed with signal 9
86 Runtime error 624 ms 65540 KB Execution killed with signal 9
87 Runtime error 607 ms 65540 KB Execution killed with signal 9
88 Runtime error 852 ms 65540 KB Execution killed with signal 9
89 Runtime error 892 ms 65540 KB Execution killed with signal 9
90 Runtime error 837 ms 65540 KB Execution killed with signal 9
91 Runtime error 832 ms 65536 KB Execution killed with signal 9
92 Runtime error 856 ms 65540 KB Execution killed with signal 9