Submission #1038566

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1038566	2024-07-30T01:58:50 Z	Tepeyac	Mecho (IOI09_mecho)	C++11	15 / 100	203 ms	10136 KB

mecho

#include <bits/stdc++.h>

using namespace std;

struct Cell
{

int x, y, p;

};

int n;
int 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;

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

while(!q.empty())
{
    Cell Nodo;
    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') break;

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

        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(make_pair(i, j));
            enj[i][j] = 0;
        }
        else
        {
            enj[i][j] = INT_MAX;
        }
        if(ma[i][j] == 'M')
        {
            pos.first = i;
            pos.second = 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(make_pair(nx, ny));
            enj[nx][ny] = enj[i2][j2] + 1;
        }
    }
}

int maxx = enj[pos.first][pos.second];

cout << BSOTA(0, maxx - 2);





}

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Incorrect	0 ms	348 KB	Output isn't correct
5	Correct	0 ms	348 KB	Output is correct
6	Incorrect	0 ms	344 KB	Output isn't correct
7	Runtime error	20 ms	7828 KB	Execution killed with signal 11
8	Incorrect	0 ms	348 KB	Output isn't correct
9	Incorrect	0 ms	348 KB	Output isn't correct
10	Incorrect	0 ms	344 KB	Output isn't correct
11	Correct	0 ms	344 KB	Output is correct
12	Incorrect	0 ms	2652 KB	Output isn't correct
13	Correct	0 ms	604 KB	Output is correct
14	Incorrect	1 ms	604 KB	Output isn't correct
15	Correct	0 ms	348 KB	Output is correct
16	Incorrect	0 ms	348 KB	Output isn't correct
17	Correct	0 ms	348 KB	Output is correct
18	Incorrect	1 ms	348 KB	Output isn't correct
19	Correct	0 ms	348 KB	Output is correct
20	Incorrect	1 ms	604 KB	Output isn't correct
21	Correct	0 ms	604 KB	Output is correct
22	Runtime error	1 ms	860 KB	Execution killed with signal 11
23	Correct	0 ms	604 KB	Output is correct
24	Runtime error	1 ms	860 KB	Execution killed with signal 11
25	Correct	1 ms	604 KB	Output is correct
26	Runtime error	1 ms	1116 KB	Execution killed with signal 11
27	Correct	0 ms	604 KB	Output is correct
28	Runtime error	1 ms	1116 KB	Execution killed with signal 11
29	Correct	1 ms	604 KB	Output is correct
30	Runtime error	1 ms	1116 KB	Execution killed with signal 11
31	Correct	1 ms	604 KB	Output is correct
32	Runtime error	1 ms	1272 KB	Execution killed with signal 11
33	Correct	6 ms	1784 KB	Output is correct
34	Runtime error	5 ms	4200 KB	Execution killed with signal 11
35	Runtime error	4 ms	3420 KB	Execution killed with signal 11
36	Correct	5 ms	2140 KB	Output is correct
37	Runtime error	6 ms	4848 KB	Execution killed with signal 11
38	Runtime error	5 ms	3932 KB	Execution killed with signal 11
39	Correct	11 ms	2396 KB	Output is correct
40	Runtime error	10 ms	7276 KB	Execution killed with signal 11
41	Runtime error	6 ms	4188 KB	Execution killed with signal 11
42	Correct	8 ms	2652 KB	Output is correct
43	Runtime error	9 ms	6368 KB	Execution killed with signal 11
44	Runtime error	7 ms	5992 KB	Execution killed with signal 11
45	Correct	9 ms	2908 KB	Output is correct
46	Runtime error	9 ms	7164 KB	Execution killed with signal 11
47	Runtime error	8 ms	5212 KB	Execution killed with signal 11
48	Correct	11 ms	3176 KB	Output is correct
49	Runtime error	12 ms	8596 KB	Execution killed with signal 11
50	Runtime error	13 ms	6232 KB	Execution killed with signal 11
51	Correct	13 ms	3420 KB	Output is correct
52	Runtime error	14 ms	10136 KB	Execution killed with signal 11
53	Runtime error	11 ms	6004 KB	Execution killed with signal 11
54	Correct	15 ms	3676 KB	Output is correct
55	Runtime error	11 ms	6492 KB	Execution killed with signal 11
56	Runtime error	18 ms	6484 KB	Execution killed with signal 11
57	Correct	21 ms	3932 KB	Output is correct
58	Runtime error	14 ms	7004 KB	Execution killed with signal 11
59	Runtime error	15 ms	7028 KB	Execution killed with signal 11
60	Correct	20 ms	4224 KB	Output is correct
61	Runtime error	14 ms	7516 KB	Execution killed with signal 11
62	Runtime error	21 ms	7436 KB	Execution killed with signal 11
63	Runtime error	21 ms	7504 KB	Execution killed with signal 11
64	Incorrect	23 ms	4188 KB	Output isn't correct
65	Runtime error	21 ms	7516 KB	Execution killed with signal 11
66	Runtime error	22 ms	7548 KB	Execution killed with signal 11
67	Runtime error	20 ms	7516 KB	Execution killed with signal 11
68	Runtime error	34 ms	7832 KB	Execution killed with signal 11
69	Runtime error	23 ms	7580 KB	Execution killed with signal 11
70	Runtime error	203 ms	8664 KB	Execution killed with signal 11
71	Runtime error	130 ms	8880 KB	Execution killed with signal 11
72	Runtime error	25 ms	7508 KB	Execution killed with signal 11
73	Incorrect	16 ms	4440 KB	Output isn't correct
74	Runtime error	20 ms	8024 KB	Execution killed with signal 11
75	Runtime error	20 ms	8084 KB	Execution killed with signal 11
76	Runtime error	20 ms	8028 KB	Execution killed with signal 11
77	Runtime error	20 ms	8084 KB	Execution killed with signal 11
78	Runtime error	20 ms	8028 KB	Execution killed with signal 11
79	Runtime error	30 ms	8048 KB	Execution killed with signal 11
80	Runtime error	20 ms	8020 KB	Execution killed with signal 11
81	Runtime error	23 ms	8028 KB	Execution killed with signal 11
82	Runtime error	20 ms	8020 KB	Execution killed with signal 11
83	Runtime error	20 ms	8028 KB	Execution killed with signal 11
84	Runtime error	20 ms	8028 KB	Execution killed with signal 11
85	Runtime error	25 ms	8028 KB	Execution killed with signal 11
86	Runtime error	21 ms	8224 KB	Execution killed with signal 11
87	Runtime error	21 ms	7912 KB	Execution killed with signal 11
88	Runtime error	26 ms	7768 KB	Execution killed with signal 11
89	Runtime error	20 ms	7680 KB	Execution killed with signal 11
90	Runtime error	24 ms	7764 KB	Execution killed with signal 11
91	Runtime error	20 ms	7768 KB	Execution killed with signal 11
92	Runtime error	21 ms	7712 KB	Execution killed with signal 11