Submission #1229384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229384		kunzaZa183	Mecho (IOI09_mecho)	C++20	96 / 100	550 ms	6876 KiB

mecho

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, s;
  cin >> n >> s;
  vector<string> vs(n);
  for (auto &a : vs)
    cin >> a;

  vector<pair<int, int>> hs2, ms2;
  int xd, yd;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (vs[i][j] == 'M')
        ms2.emplace_back(i, j);
      else if (vs[i][j] == 'D')
        xd = i, yd = j;
      else if (vs[i][j] == 'H')
        hs2.emplace_back(i, j);

  vector<vector<int>> status; // G = 0, M = 1, H = 2
  vector<pair<int, int>> hs, ms;
  const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

  auto mwalk = [&]() {
    vector<pair<int, int>> newms;

    for (auto [x, y] : ms) {

      if (status[x][y] != 0)
        continue;

      status[x][y] = 1;

      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];

        if (nx >= 0 && nx < n && ny >= 0 && ny < n && status[nx][ny] == 0 &&
            (vs[nx][ny] == 'G' || vs[nx][ny] == 'D'))
          newms.emplace_back(nx, ny);
      }
    }

    ms.swap(newms);
  };

  auto hwalk = [&]() {
    vector<pair<int, int>> newhs;

    for (auto [x, y] : hs) {

      if (status[x][y] == 2)
        continue;

      status[x][y] = 2;

      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];

        if (nx >= 0 && nx < n && ny >= 0 && ny < n && status[nx][ny] != 2 &&
            (vs[nx][ny] == 'G' || vs[nx][ny] == 'M'))
          newhs.emplace_back(nx, ny);
      }
    }

    hs.swap(newhs);
  };

  int l = 0, r = 1e9;
  while (l < r) {
    int mid = (l + r + 1) / 2;

    //cout << mid << "\n";

    status = vector<vector<int>>(n, vector<int>(n, 0)); // 0 = G, 1 = M, 2 = H

    hs = hs2, ms = ms2;

     hwalk();

    for (int i = 0; i < mid && !hs.empty(); i++)
      hwalk();

    //for (auto a : status) {
    //  for (auto b : a)
    //    cout << b << " ";
    //  cout << "\n";
    //}
    //cout << "\n";

    while (!ms.empty()) {
      for (int i = 0; i < s && !ms.empty(); i++)
        mwalk();
      hwalk();

      //for (auto a : status) {
      //  for (auto b : a)
      //    cout << b << " ";
      //  cout << "\n";
      //}
      //cout << "\n";
    }

    if (status[xd][yd] == 0) {
      r = mid - 1;
    } else {
      l = mid;
    }
  }

  status = vector<vector<int>>(n, vector<int>(n, 0)); // 0 = G, 1 = M, 2 = H

  hs = hs2, ms = ms2;

  mwalk(), hwalk();

  for (int i = 0; i < l && !hs.empty(); i++)
    hwalk();

  while (!ms.empty()) {
    for (int i = 0; i < s && !ms.empty(); i++)
      mwalk();
    hwalk();
  }

  if (status[xd][yd] == 0) {
    cout << "-1\n";
  } else {
    cout << l << "\n";
  }
}

• Subtask 1: 96 / 100