oj.uz

답안 #1038568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1038568 2024-07-30T02:04:29 Z Tepeyac Mecho (IOI09_mecho) C++11
15 / 100
 1000 ms 7040 KB 
#include <bits/stdc++.h>

using namespace std;

struct Cell {
    int x, y, p;
};

int n, s;
char ma[801][801];
int enj[801][801];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool isvalid(int i, int j) {
    return i >= 1 && i <= n && j >= 1 && j <= n; 
}

bool monotone(int m) {
    queue<Cell> q;
    char temp_ma[801][801];
    memcpy(temp_ma, ma, sizeof(ma));

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            if(temp_ma[i][j] == 'M') {
                Cell nodo = {i, j, 0};
                q.push(nodo);
            }
        }
    }

    while(!q.empty()) {
        Cell Nodo = q.front();
        q.pop();

        for(int i = 0; i < 4; ++i) {
            for(int j = 1; j <= s; ++j) {
                int nx = Nodo.x + j * dx[i];
                int ny = Nodo.y + j * dy[i];

                if(!isvalid(nx, ny) || temp_ma[nx][ny] == 'H' || temp_ma[nx][ny] == 'T') 
                    break;

                if(m <= enj[nx][ny] && temp_ma[nx][ny] != 'M') {
                    if(temp_ma[nx][ny] == 'D') {
                        return true;
                    }

                    temp_ma[nx][ny] = 'M';
                    q.push({nx, ny, Nodo.p + 1});
                }
            }
        }
    }

    return false;
}

int BSOTA(int a, int b) {
    while(a + 1 < b) {
        int m = (a + b) / 2;
        if(monotone(m)) {
            a = m;
        } else {
            b = m;
        }
    }
    return a;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n >> s;

    pair<int, int> pos;
    queue<pair<int, int>> q;

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            cin >> ma[i][j];
            if(ma[i][j] == 'H') {
                q.push({i, j});
                enj[i][j] = 0;
            } else {
                enj[i][j] = INT_MAX;
            }
            if(ma[i][j] == 'M') {
                pos = {i, j};
            }
        }
    }

    while(!q.empty()) {
        int i2 = q.front().first, j2 = q.front().second;
        q.pop();

        for(int i = 0; i < 4; ++i) {
            int nx = dx[i] + i2;
            int ny = dy[i] + j2;

            if(isvalid(nx, ny) && ma[nx][ny] != 'D' && ma[nx][ny] != 'T' && ma[nx][ny] != 'H' && enj[nx][ny] == INT_MAX) {
                q.push({nx, ny});
                enj[nx][ny] = enj[i2][j2] + 1;
            }
        }
    }

    int maxx = enj[pos.first][pos.second];
   
        cout << BSOTA(0, maxx - 2) << "\n";
    
    return 0;
}

Subtask #1
15.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 856 KB Output is correct
2 Incorrect 1 ms 856 KB Output isn't correct
3 Incorrect 1 ms 860 KB Output isn't correct
4 Incorrect 1 ms 860 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 908 KB Output isn't correct
7 Execution timed out 1096 ms 4968 KB Time limit exceeded
8 Incorrect 1 ms 1116 KB Output isn't correct
9 Incorrect 1 ms 1116 KB Output isn't correct
10 Incorrect 1 ms 1116 KB Output isn't correct
11 Correct 1 ms 1144 KB Output is correct
12 Incorrect 1 ms 3160 KB Output isn't correct
13 Correct 0 ms 600 KB Output is correct
14 Incorrect 2 ms 3164 KB Output isn't correct
15 Correct 1 ms 1112 KB Output is correct
16 Incorrect 1 ms 1116 KB Output isn't correct
17 Correct 1 ms 1116 KB Output is correct
18 Incorrect 1 ms 1116 KB Output isn't correct
19 Correct 1 ms 976 KB Output is correct
20 Incorrect 1 ms 1116 KB Output isn't correct
21 Correct 1 ms 1116 KB Output is correct
22 Incorrect 1 ms 1112 KB Output isn't correct
23 Correct 1 ms 1116 KB Output is correct
24 Incorrect 1 ms 1116 KB Output isn't correct
25 Correct 1 ms 3164 KB Output is correct
26 Incorrect 2 ms 1112 KB Output isn't correct
27 Correct 1 ms 1116 KB Output is correct
28 Incorrect 1 ms 1288 KB Output isn't correct
29 Correct 1 ms 3164 KB Output is correct
30 Incorrect 2 ms 1372 KB Output isn't correct
31 Correct 1 ms 1228 KB Output is correct
32 Incorrect 1 ms 1372 KB Output isn't correct
33 Correct 7 ms 2396 KB Output is correct
34 Incorrect 7 ms 2524 KB Output isn't correct
35 Incorrect 817 ms 3292 KB Output isn't correct
36 Correct 6 ms 3676 KB Output is correct
37 Incorrect 9 ms 2652 KB Output isn't correct
38 Execution timed out 1096 ms 3740 KB Time limit exceeded
39 Correct 7 ms 2904 KB Output is correct
40 Incorrect 11 ms 3012 KB Output isn't correct
41 Execution timed out 1093 ms 4240 KB Time limit exceeded
42 Correct 10 ms 3928 KB Output is correct
43 Incorrect 11 ms 3928 KB Output isn't correct
44 Execution timed out 1096 ms 4684 KB Time limit exceeded
45 Correct 9 ms 3928 KB Output is correct
46 Incorrect 14 ms 3420 KB Output isn't correct
47 Execution timed out 1042 ms 5156 KB Time limit exceeded
48 Correct 11 ms 3672 KB Output is correct
49 Incorrect 16 ms 3676 KB Output isn't correct
50 Execution timed out 1049 ms 5348 KB Time limit exceeded
51 Correct 13 ms 3928 KB Output is correct
52 Incorrect 19 ms 3932 KB Output isn't correct
53 Execution timed out 1095 ms 5928 KB Time limit exceeded
54 Correct 21 ms 4184 KB Output is correct
55 Incorrect 22 ms 4184 KB Output isn't correct
56 Execution timed out 1053 ms 6528 KB Time limit exceeded
57 Correct 18 ms 4440 KB Output is correct
58 Incorrect 29 ms 4468 KB Output isn't correct
59 Execution timed out 1096 ms 6568 KB Time limit exceeded
60 Correct 21 ms 4700 KB Output is correct
61 Incorrect 32 ms 4836 KB Output isn't correct
62 Execution timed out 1041 ms 7040 KB Time limit exceeded
63 Incorrect 99 ms 4692 KB Output isn't correct
64 Incorrect 157 ms 4692 KB Output isn't correct
65 Incorrect 157 ms 4692 KB Output isn't correct
66 Incorrect 116 ms 4700 KB Output isn't correct
67 Incorrect 152 ms 4724 KB Output isn't correct
68 Incorrect 38 ms 4700 KB Output isn't correct
69 Incorrect 48 ms 4856 KB Output isn't correct
70 Incorrect 37 ms 4692 KB Output isn't correct
71 Incorrect 39 ms 4768 KB Output isn't correct
72 Incorrect 27 ms 4756 KB Output isn't correct
73 Incorrect 22 ms 4700 KB Output isn't correct
74 Execution timed out 1091 ms 5720 KB Time limit exceeded
75 Incorrect 205 ms 5104 KB Output isn't correct
76 Incorrect 120 ms 5108 KB Output isn't correct
77 Incorrect 378 ms 5100 KB Output isn't correct
78 Incorrect 407 ms 5080 KB Output isn't correct
79 Execution timed out 1062 ms 5976 KB Time limit exceeded
80 Incorrect 245 ms 5080 KB Output isn't correct
81 Incorrect 189 ms 5000 KB Output isn't correct
82 Incorrect 428 ms 5076 KB Output isn't correct
83 Incorrect 371 ms 5044 KB Output isn't correct
84 Execution timed out 1072 ms 6160 KB Time limit exceeded
85 Incorrect 415 ms 5040 KB Output isn't correct
86 Incorrect 394 ms 5044 KB Output isn't correct
87 Execution timed out 1012 ms 5040 KB Time limit exceeded
88 Incorrect 755 ms 4944 KB Output isn't correct
89 Execution timed out 1048 ms 6756 KB Time limit exceeded
90 Execution timed out 1042 ms 4952 KB Time limit exceeded
91 Execution timed out 1043 ms 5204 KB Time limit exceeded
92 Execution timed out 1024 ms 4988 KB Time limit exceeded