Submission #1208591

#TimeUsernameProblemLanguageResultExecution timeMemory
1208591timeflewMecho (IOI09_mecho)C++20
27 / 100
129 ms4512 KiB
//grok debugging #include <bits/stdc++.h> using namespace std; const int mxN = 8e2; char c[mxN][mxN]; int vis[mxN][mxN]; bool vis1[mxN][mxN]; pair<int, int> st, ed; int n, s; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; bool mecho_valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n && (c[x][y] == 'G' || c[x][y] == 'M' || c[x][y] == 'D'); } bool bee_valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n && (c[x][y] == 'G' || c[x][y] == 'M'); } bool check(int x) { if (vis[st.first][st.second] <= x) return 0; // Bees reach 'M' during eating queue<array<int, 4>> q; // {x, y, minute, steps_in_minute} q.push({st.first, st.second, x + 1, 0}); memset(vis1, 0, sizeof(vis1)); vis1[st.first][st.second] = 1; while (!q.empty()) { auto [xx, yy, step, state] = q.front(); q.pop(); if (xx == ed.first && yy == ed.second) return 1; for (int i = 0; i < 4; i++) { int nx = xx + dx[i], ny = yy + dy[i]; if (mecho_valid(nx, ny) && vis[nx][ny] > step && !vis1[nx][ny]) { vis1[nx][ny] = 1; if (state + 1 == s) { q.push({nx, ny, step + 1, 0}); } else { q.push({nx, ny, step, state + 1}); } } } } return 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> s; queue<array<int, 3>> q; memset(vis, 0x3f, sizeof(vis)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> c[i][j]; if (c[i][j] == 'M') st = {i, j}; if (c[i][j] == 'D') ed = {i, j}; if (c[i][j] == 'H') q.push({i, j, 0}), vis[i][j] = 0; } } while (!q.empty()) { auto [x, y, now] = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (bee_valid(nx, ny) && vis[nx][ny] == 0x3f3f3f3f) { vis[nx][ny] = now + 1; q.push({nx, ny, now + 1}); } } } int l = 0, r = n * n, ans = -1; while (l <= r) { int mid = (l + r) / 2; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...