oj.uz

Submission #482485

# Submission time Handle Problem Language Result Execution time Memory
482485 2021-10-24T20:43: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 2876 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 4 ms 2892 KB Output isn't correct
7 Execution timed out 1056 ms 65540 KB Time limit exceeded
8 Incorrect 12 ms 2940 KB Output isn't correct
9 Correct 11 ms 2892 KB Output is correct
10 Correct 12 ms 2892 KB Output is correct
11 Correct 11 ms 2892 KB Output is correct
12 Incorrect 758 ms 3344 KB Output isn't correct
13 Execution timed out 1091 ms 3828 KB Time limit exceeded
14 Execution timed out 1089 ms 3964 KB Time limit exceeded
15 Incorrect 9 ms 2892 KB Output isn't correct
16 Correct 15 ms 2924 KB Output is correct
17 Incorrect 11 ms 2960 KB Output isn't correct
18 Correct 26 ms 2892 KB Output is correct
19 Incorrect 19 ms 2964 KB Output isn't correct
20 Correct 53 ms 2892 KB Output is correct
21 Incorrect 53 ms 2976 KB Output isn't correct
22 Correct 201 ms 3140 KB Output is correct
23 Incorrect 127 ms 3128 KB Output isn't correct
24 Correct 472 ms 3196 KB Output is correct
25 Incorrect 264 ms 3276 KB Output isn't correct
26 Execution timed out 1091 ms 3336 KB Time limit exceeded
27 Incorrect 364 ms 3348 KB Output isn't correct
28 Execution timed out 1092 ms 3732 KB Time limit exceeded
29 Incorrect 528 ms 3844 KB Output isn't correct
30 Execution timed out 1093 ms 3920 KB Time limit exceeded
31 Incorrect 688 ms 3524 KB Output isn't correct
32 Execution timed out 1088 ms 3428 KB Time limit exceeded
33 Execution timed out 1086 ms 4136 KB Time limit exceeded
34 Execution timed out 1048 ms 4448 KB Time limit exceeded
35 Execution timed out 1092 ms 16940 KB Time limit exceeded
36 Execution timed out 1076 ms 4060 KB Time limit exceeded
37 Execution timed out 1085 ms 4680 KB Time limit exceeded
38 Execution timed out 1088 ms 16900 KB Time limit exceeded
39 Execution timed out 1093 ms 4284 KB Time limit exceeded
40 Execution timed out 1085 ms 4688 KB Time limit exceeded
41 Execution timed out 1093 ms 17072 KB Time limit exceeded
42 Execution timed out 1046 ms 4360 KB Time limit exceeded
43 Execution timed out 1084 ms 4944 KB Time limit exceeded
44 Execution timed out 1085 ms 17216 KB Time limit exceeded
45 Execution timed out 1090 ms 4480 KB Time limit exceeded
46 Execution timed out 1088 ms 4656 KB Time limit exceeded
47 Execution timed out 1097 ms 17408 KB Time limit exceeded
48 Execution timed out 1077 ms 4676 KB Time limit exceeded
49 Execution timed out 1090 ms 4764 KB Time limit exceeded
50 Execution timed out 1085 ms 17668 KB Time limit exceeded
51 Execution timed out 1087 ms 4652 KB Time limit exceeded
52 Execution timed out 1096 ms 4768 KB Time limit exceeded
53 Execution timed out 1096 ms 17732 KB Time limit exceeded
54 Execution timed out 1092 ms 4664 KB Time limit exceeded
55 Execution timed out 1092 ms 5132 KB Time limit exceeded
56 Execution timed out 1094 ms 17688 KB Time limit exceeded
57 Execution timed out 1094 ms 4800 KB Time limit exceeded
58 Execution timed out 1094 ms 5116 KB Time limit exceeded
59 Execution timed out 1088 ms 18108 KB Time limit exceeded
60 Execution timed out 1057 ms 4940 KB Time limit exceeded
61 Execution timed out 1094 ms 5140 KB Time limit exceeded
62 Execution timed out 1059 ms 17832 KB Time limit exceeded
63 Execution timed out 1093 ms 8680 KB Time limit exceeded
64 Execution timed out 1094 ms 8272 KB Time limit exceeded
65 Execution timed out 1096 ms 8332 KB Time limit exceeded
66 Execution timed out 1095 ms 8844 KB Time limit exceeded
67 Execution timed out 1099 ms 8692 KB Time limit exceeded
68 Execution timed out 1099 ms 33680 KB Time limit exceeded
69 Execution timed out 1100 ms 33492 KB Time limit exceeded
70 Execution timed out 1095 ms 33544 KB Time limit exceeded
71 Execution timed out 1101 ms 33556 KB Time limit exceeded
72 Execution timed out 1101 ms 33548 KB Time limit exceeded
73 Runtime error 528 ms 65540 KB Execution killed with signal 9
74 Runtime error 523 ms 65540 KB Execution killed with signal 9
75 Runtime error 523 ms 65540 KB Execution killed with signal 9
76 Runtime error 521 ms 65540 KB Execution killed with signal 9
77 Runtime error 525 ms 65540 KB Execution killed with signal 9
78 Runtime error 539 ms 65540 KB Execution killed with signal 9
79 Runtime error 540 ms 65540 KB Execution killed with signal 9
80 Runtime error 551 ms 65540 KB Execution killed with signal 9
81 Runtime error 545 ms 65540 KB Execution killed with signal 9
82 Runtime error 548 ms 65540 KB Execution killed with signal 9
83 Runtime error 611 ms 65540 KB Execution killed with signal 9
84 Runtime error 608 ms 65540 KB Execution killed with signal 9
85 Runtime error 599 ms 65540 KB Execution killed with signal 9
86 Runtime error 605 ms 65540 KB Execution killed with signal 9
87 Runtime error 609 ms 65540 KB Execution killed with signal 9
88 Runtime error 828 ms 65540 KB Execution killed with signal 9
89 Runtime error 835 ms 65540 KB Execution killed with signal 9
90 Runtime error 834 ms 65540 KB Execution killed with signal 9
91 Runtime error 822 ms 65540 KB Execution killed with signal 9
92 Runtime error 822 ms 65540 KB Execution killed with signal 9