답안 #1038569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038569	2024-07-30T02:10:11 Z	Tepeyac	Mecho (IOI09_mecho)	C++11	8 / 100	1000 ms	6228 KB

mecho

#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) << "\n";
    
    return 0;
}

Subtask #1

8.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	856 KB	Output isn't correct
2	Incorrect	1 ms	860 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	Incorrect	1 ms	1116 KB	Output isn't correct
6	Incorrect	1 ms	1116 KB	Output isn't correct
7	Execution timed out	1100 ms	4452 KB	Time limit exceeded
8	Incorrect	1 ms	1116 KB	Output isn't correct
9	Correct	1 ms	940 KB	Output is correct
10	Incorrect	1 ms	1116 KB	Output isn't correct
11	Incorrect	1 ms	1116 KB	Output isn't correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	0 ms	604 KB	Output is correct
14	Incorrect	1 ms	1116 KB	Output isn't correct
15	Incorrect	1 ms	1116 KB	Output isn't correct
16	Incorrect	1 ms	1116 KB	Output isn't correct
17	Incorrect	1 ms	1116 KB	Output isn't correct
18	Incorrect	1 ms	1116 KB	Output isn't correct
19	Incorrect	1 ms	1116 KB	Output isn't correct
20	Incorrect	1 ms	1116 KB	Output isn't correct
21	Incorrect	1 ms	1116 KB	Output isn't correct
22	Incorrect	1 ms	1116 KB	Output isn't correct
23	Incorrect	1 ms	1116 KB	Output isn't correct
24	Incorrect	1 ms	1116 KB	Output isn't correct
25	Incorrect	1 ms	1116 KB	Output isn't correct
26	Incorrect	1 ms	1116 KB	Output isn't correct
27	Incorrect	1 ms	3160 KB	Output isn't correct
28	Incorrect	1 ms	1116 KB	Output isn't correct
29	Incorrect	1 ms	1372 KB	Output isn't correct
30	Incorrect	1 ms	1372 KB	Output isn't correct
31	Incorrect	1 ms	1368 KB	Output isn't correct
32	Incorrect	1 ms	1368 KB	Output isn't correct
33	Incorrect	4 ms	2396 KB	Output isn't correct
34	Incorrect	7 ms	2392 KB	Output isn't correct
35	Incorrect	992 ms	3140 KB	Output isn't correct
36	Incorrect	6 ms	2652 KB	Output isn't correct
37	Incorrect	8 ms	2652 KB	Output isn't correct
38	Execution timed out	1096 ms	3560 KB	Time limit exceeded
39	Incorrect	8 ms	2652 KB	Output isn't correct
40	Incorrect	11 ms	2648 KB	Output isn't correct
41	Execution timed out	1098 ms	3992 KB	Time limit exceeded
42	Incorrect	9 ms	3160 KB	Output isn't correct
43	Incorrect	13 ms	3052 KB	Output isn't correct
44	Execution timed out	1100 ms	4296 KB	Time limit exceeded
45	Incorrect	10 ms	3672 KB	Output isn't correct
46	Incorrect	15 ms	3676 KB	Output isn't correct
47	Execution timed out	1098 ms	4828 KB	Time limit exceeded
48	Incorrect	12 ms	3416 KB	Output isn't correct
49	Incorrect	19 ms	3420 KB	Output isn't correct
50	Execution timed out	1041 ms	5000 KB	Time limit exceeded
51	Incorrect	14 ms	3416 KB	Output isn't correct
52	Incorrect	22 ms	3624 KB	Output isn't correct
53	Execution timed out	1072 ms	5672 KB	Time limit exceeded
54	Incorrect	15 ms	3676 KB	Output isn't correct
55	Incorrect	24 ms	3616 KB	Output isn't correct
56	Execution timed out	1012 ms	5540 KB	Time limit exceeded
57	Incorrect	20 ms	3928 KB	Output isn't correct
58	Incorrect	30 ms	3912 KB	Output isn't correct
59	Execution timed out	1083 ms	5776 KB	Time limit exceeded
60	Incorrect	21 ms	4184 KB	Output isn't correct
61	Incorrect	33 ms	4188 KB	Output isn't correct
62	Execution timed out	1043 ms	6228 KB	Time limit exceeded
63	Incorrect	139 ms	4188 KB	Output isn't correct
64	Incorrect	171 ms	4188 KB	Output isn't correct
65	Incorrect	173 ms	4184 KB	Output isn't correct
66	Incorrect	126 ms	4204 KB	Output isn't correct
67	Incorrect	156 ms	4208 KB	Output isn't correct
68	Incorrect	40 ms	4120 KB	Output isn't correct
69	Incorrect	40 ms	4184 KB	Output isn't correct
70	Incorrect	39 ms	4136 KB	Output isn't correct
71	Incorrect	42 ms	4176 KB	Output isn't correct
72	Correct	35 ms	4188 KB	Output is correct
73	Correct	76 ms	4384 KB	Output is correct
74	Execution timed out	1056 ms	5180 KB	Time limit exceeded
75	Incorrect	170 ms	4440 KB	Output isn't correct
76	Incorrect	109 ms	4440 KB	Output isn't correct
77	Incorrect	332 ms	4688 KB	Output isn't correct
78	Incorrect	405 ms	4432 KB	Output isn't correct
79	Execution timed out	1059 ms	5484 KB	Time limit exceeded
80	Incorrect	277 ms	4456 KB	Output isn't correct
81	Incorrect	208 ms	4444 KB	Output isn't correct
82	Incorrect	468 ms	4452 KB	Output isn't correct
83	Incorrect	400 ms	4188 KB	Output isn't correct
84	Execution timed out	1070 ms	5336 KB	Time limit exceeded
85	Incorrect	508 ms	4412 KB	Output isn't correct
86	Incorrect	418 ms	4184 KB	Output isn't correct
87	Execution timed out	1020 ms	4432 KB	Time limit exceeded
88	Incorrect	750 ms	4276 KB	Output isn't correct
89	Execution timed out	1016 ms	5968 KB	Time limit exceeded
90	Execution timed out	1046 ms	4184 KB	Time limit exceeded
91	Execution timed out	1038 ms	4688 KB	Time limit exceeded
92	Incorrect	958 ms	4440 KB	Output isn't correct