답안 #482485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482485	2021-10-24T20:43:44 Z	danielsuh	Mecho (IOI09_mecho)	C++17	7 / 100	1000 ms	65540 KB

mecho

#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

#	결과	실행 시간	메모리	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