oj.uz

Submission #1038602

# Submission time Handle Problem Language Result Execution time Memory
1038602 2024-07-30T03:25:13 Z Tepeyac Mecho (IOI09_mecho) C++11
15 / 100
 185 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

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

int n, s;
pair<int, int> pos;
char ma[802][802];
int enj[802][802];
bool vb[802][802];

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;

    memset(vb, false, sizeof(vb));

    /*for(int i = 1; i <= n; ++i) 
    {
        for(int j = 1; j <= n; ++j) 
        {
            if(ma[i][j] == 'M') 
            {
                Cell nodo = {i, j, m};
                q.push(nodo);
                vb[i][j] = true;
            }
        }
    }*/

   Cell nodo = {pos.first, pos.second, m};
   q.push(nodo);
   vb[pos.first][pos.second] = true;

    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) || ma[nx][ny] == 'H' || ma[nx][ny] == 'T' && Nodo.p + 1 >= enj[nx][ny] && vb[nx][ny]) 
                    break;

                    if(ma[nx][ny] == 'D') 
                    {
                        return true;
                    }

                    vb[nx][ny] = true;
                    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;

    
    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] = -1;
            }
            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] == -1) 
            {
                q.push({nx, ny});
                enj[nx][ny] = enj[i2][j2] + 1;
            }
        }
    }

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

Compilation message

mecho.cpp: In function 'bool monotone(int)':
mecho.cpp:59:108: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   59 |                 if(!isvalid(nx, ny) || ma[nx][ny] == 'H' || ma[nx][ny] == 'T' && Nodo.p + 1 >= enj[nx][ny] && vb[nx][ny])
      |                                                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
mecho.cpp:59:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   59 |                 if(!isvalid(nx, ny) || ma[nx][ny] == 'H' || ma[nx][ny] == 'T' && Nodo.p + 1 >= enj[nx][ny] && vb[nx][ny])
      |                 ^~
mecho.cpp:62:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   62 |                     if(ma[nx][ny] == 'D')
      |                     ^~

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Incorrect 1 ms 1116 KB Output isn't correct
3 Incorrect 1 ms 1112 KB Output isn't correct
4 Incorrect 1 ms 1116 KB Output isn't correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 1 ms 1116 KB Output isn't correct
7 Runtime error 65 ms 65536 KB Execution killed with signal 9
8 Runtime error 74 ms 65536 KB Execution killed with signal 9
9 Incorrect 1 ms 1112 KB Output isn't correct
10 Incorrect 11 ms 3680 KB Output isn't correct
11 Correct 1 ms 1116 KB Output is correct
12 Incorrect 1 ms 1116 KB Output isn't correct
13 Correct 1 ms 600 KB Output is correct
14 Runtime error 56 ms 65536 KB Execution killed with signal 9
15 Correct 1 ms 1112 KB Output is correct
16 Incorrect 1 ms 1116 KB Output isn't correct
17 Correct 1 ms 1112 KB Output is correct
18 Incorrect 1 ms 1116 KB Output isn't correct
19 Correct 1 ms 1116 KB Output is correct
20 Incorrect 1 ms 1116 KB Output isn't correct
21 Correct 1 ms 1232 KB Output is correct
22 Incorrect 1 ms 1116 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 1116 KB Output is correct
26 Incorrect 1 ms 1372 KB Output isn't correct
27 Correct 1 ms 1116 KB Output is correct
28 Incorrect 1 ms 1160 KB Output isn't correct
29 Correct 1 ms 1372 KB Output is correct
30 Incorrect 1 ms 1372 KB Output isn't correct
31 Correct 1 ms 1372 KB Output is correct
32 Incorrect 1 ms 1372 KB Output isn't correct
33 Correct 3 ms 2396 KB Output is correct
34 Incorrect 11 ms 3536 KB Output isn't correct
35 Runtime error 55 ms 65536 KB Execution killed with signal 9
36 Correct 4 ms 2652 KB Output is correct
37 Incorrect 15 ms 4060 KB Output isn't correct
38 Runtime error 55 ms 65536 KB Execution killed with signal 9
39 Correct 8 ms 2908 KB Output is correct
40 Incorrect 19 ms 4612 KB Output isn't correct
41 Runtime error 54 ms 65536 KB Execution killed with signal 9
42 Correct 6 ms 3164 KB Output is correct
43 Incorrect 23 ms 5228 KB Output isn't correct
44 Runtime error 53 ms 65536 KB Execution killed with signal 9
45 Correct 6 ms 3416 KB Output is correct
46 Incorrect 31 ms 5852 KB Output isn't correct
47 Runtime error 56 ms 65536 KB Execution killed with signal 9
48 Correct 7 ms 3672 KB Output is correct
49 Incorrect 34 ms 6588 KB Output isn't correct
50 Runtime error 56 ms 65536 KB Execution killed with signal 9
51 Correct 8 ms 3928 KB Output is correct
52 Incorrect 47 ms 7308 KB Output isn't correct
53 Runtime error 57 ms 65536 KB Execution killed with signal 9
54 Correct 10 ms 4184 KB Output is correct
55 Incorrect 52 ms 8120 KB Output isn't correct
56 Runtime error 58 ms 65536 KB Execution killed with signal 9
57 Correct 10 ms 4444 KB Output is correct
58 Incorrect 56 ms 8908 KB Output isn't correct
59 Runtime error 64 ms 65536 KB Execution killed with signal 9
60 Correct 12 ms 4956 KB Output is correct
61 Incorrect 64 ms 9820 KB Output isn't correct
62 Runtime error 58 ms 65536 KB Execution killed with signal 9
63 Runtime error 101 ms 65536 KB Execution killed with signal 9
64 Incorrect 106 ms 12532 KB Output isn't correct
65 Runtime error 86 ms 65536 KB Execution killed with signal 9
66 Runtime error 93 ms 65536 KB Execution killed with signal 9
67 Runtime error 96 ms 65536 KB Execution killed with signal 9
68 Incorrect 185 ms 21644 KB Output isn't correct
69 Incorrect 30 ms 6052 KB Output isn't correct
70 Runtime error 83 ms 65536 KB Execution killed with signal 9
71 Runtime error 83 ms 65536 KB Execution killed with signal 9
72 Incorrect 37 ms 6640 KB Output isn't correct
73 Incorrect 18 ms 4444 KB Output isn't correct
74 Runtime error 65 ms 65536 KB Execution killed with signal 9
75 Runtime error 73 ms 65536 KB Execution killed with signal 9
76 Runtime error 78 ms 65536 KB Execution killed with signal 9
77 Runtime error 93 ms 65536 KB Execution killed with signal 9
78 Runtime error 73 ms 65536 KB Execution killed with signal 9
79 Runtime error 93 ms 65536 KB Execution killed with signal 9
80 Runtime error 76 ms 65536 KB Execution killed with signal 9
81 Runtime error 73 ms 65536 KB Execution killed with signal 9
82 Runtime error 71 ms 65536 KB Execution killed with signal 9
83 Runtime error 75 ms 65536 KB Execution killed with signal 9
84 Runtime error 100 ms 65536 KB Execution killed with signal 9
85 Runtime error 74 ms 65536 KB Execution killed with signal 9
86 Runtime error 75 ms 65536 KB Execution killed with signal 9
87 Runtime error 71 ms 65536 KB Execution killed with signal 9
88 Runtime error 72 ms 65536 KB Execution killed with signal 9
89 Runtime error 73 ms 65536 KB Execution killed with signal 9
90 Runtime error 70 ms 65536 KB Execution killed with signal 9
91 Runtime error 70 ms 65536 KB Execution killed with signal 9
92 Runtime error 73 ms 65536 KB Execution killed with signal 9