Submission #482593

#	Time	Username	Problem	Language	Result	Execution time	Memory
482593		danielsuh	Mecho (IOI09_mecho)	C++17	7 / 100	1100 ms	65540 KiB

mecho

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
const int mxN = 805;
int N, S; 
char grid[mxN][mxN], store_grid[mxN][mxN];
int dist[mxN][mxN];
pair<int, int> start, finish;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
 
bool check(int seconds) {
    // Can you just simulate the first w seconds and then find the BFS thing?
    for(auto &x : dist) for(auto &y : x) y = INT_MAX;
    for(int i = 0; i < N; i++) 
        for(int j = 0; j < N; j++)
            grid[i][j] = store_grid[i][j];
    
    bool reached_end = 0;
    for(int i = 0; i < seconds; i++) {
        vector<pair<int, int>> change;
        for(int j = 0; j < N; j++) {
            for(int k = 0; k < N; k++) {
                if(grid[j][k] == 'H') {
                    for(int it = 0; it < 4; it++) {
                        if(j - 1 >= 0 && grid[j - 1][k] != 'M' && grid[j - 1][k] != 'D' && grid[j - 1][k] != 'T') change.push_back(make_pair(j - 1, k));
                        if(j + 1 < N && grid[j + 1][k] != 'M' && grid[j + 1][k] != 'D' && grid[j + 1][k] != 'T') change.push_back(make_pair(j + 1, k));
                        if(k - 1 >= 0 && grid[j][k - 1] != 'M' && grid[j][k - 1] != 'D' && grid[j][k - 1] != 'T') change.push_back(make_pair(j, k - 1));
                        if(k + 1 < N && grid[j][k + 1] != 'M' && grid[j][k + 1] != 'D' && grid[j][k + 1] != 'T') change.push_back(make_pair(j, k + 1));
                    }
                }
            }
        }
        for(auto &x : change) grid[x.first][x.second] = 'H';
    }
    queue<pair<pair<int, int>, int>> q;
    q.push({make_pair(start.first, start.second), 0});
    dist[start.first][start.second] = 0;
    unordered_map<int, bool> considered;
    while(!q.empty()) {
        if(q.front().second % S == 0 && q.front().second != 0 && !considered[q.front().second]) {
            vector<pair<int, int>> change;
            for(int j = 0; j < N; j++) {
                for(int k = 0; k < N; k++) {
                    if(grid[j][k] == 'H') {
                        for(int it = 0; it < 4; it++) {
                            if(j - 1 >= 0 && grid[j - 1][k] != 'M' && grid[j - 1][k] != 'D' && grid[j - 1][k] != 'T') change.push_back(make_pair(j - 1, k));
                            if(j + 1 < N && grid[j + 1][k] != 'M' && grid[j + 1][k] != 'D' && grid[j + 1][k] != 'T') change.push_back(make_pair(j + 1, k));
                            if(k - 1 >= 0 && grid[j][k - 1] != 'M' && grid[j][k - 1] != 'D' && grid[j][k - 1] != 'T') change.push_back(make_pair(j, k - 1));
                            if(k + 1 < N && grid[j][k + 1] != 'M' && grid[j][k + 1] != 'D' && grid[j][k + 1] != 'T') change.push_back(make_pair(j, k + 1));
                        }
                    }
                }
            }
            for(auto &x : change) grid[x.first][x.second] = 'H';
            considered[q.front().second] = true;
            continue;
        }
        int x = q.front().first.first, y = q.front().first.second; 
        int cur_second = q.front().second;
        q.pop();
        if(grid[x][y] == 'H' || grid[x][y] == 'T') continue;
        if(grid[x][y] == 'D') return true;
        for(int i = 0; i < 4; i++) {
            if(x + dx[i] > 0 && y + dy[i] > 0 && x + dx[i] < N && y + dy[i] < N && dist[x][y] + 1 < dist[x + dx[i]][y + dy[i]]) {
                q.push({make_pair(x + dx[i], y + dy[i]), cur_second + 1});
                dist[x + dx[i]][y + dy[i]] = dist[x][y] + 1;
            }
        }
    }
    return false;
}
 
int bin_search() {
    int lo = 0, hi = N * N;
    while(lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if(check(mid)) {
            lo = mid;
        }else {
            hi = mid - 1;
        }
    }
    return lo;
}
 
void solve() {
    cin >> N >> S;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> grid[i][j];
            store_grid[i][j] = grid[i][j];
            if(grid[i][j] == 'M') {
                start.first = i, start.second = j;
            }else if(grid[i][j] == 'D') {
                finish.first = i, finish.second = j;
            }
       }
    }
    cout << bin_search() << "\n";
}
 
int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for(int i = 1; i <= T; ++i) {
        solve();
    }
}
 
 

Compilation message (stderr)

mecho.cpp: In function 'bool check(int)':
mecho.cpp:21:10: warning: unused variable 'reached_end' [-Wunused-variable]
   21 |     bool reached_end = 0;
      |          ^~~~~~~~~~~

• Subtask 1: 7 / 100