Submission #1038568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038568		Tepeyac	Mecho (IOI09_mecho)	C++11	15 / 100	1096 ms	7040 KiB

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

• Subtask 1: 15 / 100