Submission #964511

#	Time	Username	Problem	Language	Result	Execution time	Memory
964511		kilkuwu	Mars (APIO22_mars)	C++17	54 / 100	319 ms	5476 KiB

mars

#include "mars.h"

#include <bits/stdc++.h>

std::pair<int, int> get_bounds(int i, int k, int n) {
  int left = i * (2 * n + 1) / (2 * (n - k) + 1);
  int right = (i + 1) * (2 * n + 1) / (2 * (n - k) + 1);
  return {left, right};
}


std::string solve(std::vector<std::string> g) {
  int n = g.size();

  std::vector<int> used(n * n);

  auto id = [&](int x, int y) {
    return x * n + y;
  };

  auto dfs = [&](auto self, int x, int y) -> void {
    used[id(x, y)] = 1;
    if (x - 1 >= 0) {
      if (!used[id(x - 1, y)] && g[x - 1][y] == '1') {
        self(self, x - 1, y);
      } 
    }

    if (x + 1 < n) {
      if (!used[id(x + 1, y)] && g[x + 1][y] == '1') {
        self(self, x + 1, y);
      } 
    }

    if (y - 1 >= 0) {
      if (!used[id(x, y - 1)] && g[x][y - 1] == '1') {
        self(self, x, y - 1);
      } 
    }

    if (y + 1 < n) {
      if (!used[id(x, y + 1)] && g[x][y + 1] == '1') {
        self(self, x, y + 1);
      } 
    }
  };

  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!used[i * n + j] && g[i][j] == '1') {
        dfs(dfs, i, j);
        ans++;
      }
    }
  }

  std::string res;
  while (ans) {
    res.push_back((ans & 1) + '0');
    ans >>= 1;
  }

  while (res.size() < 100) {
    res.push_back('0');
  }
  return res;
}

std::string process(std::vector<std::vector<std::string>> a, int xx, int yy, int k, int n) {
  std::vector<std::string> g(2 * n + 1, std::string(2 * n + 1, '0'));

  auto regen = [&](std::string s, int x, int y) {
    auto [lx, rx] = get_bounds(x, k, n);
    auto [ly, ry] = get_bounds(y, k, n);

    for (int i = lx; i < rx; i++) {
      for (int j = ly; j < ry; j++) {
        int u = i - lx;
        int v = j - ly;
        g[i][j] = s[u * (ry - ly) + v];
      }
    }
  };

  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      regen(a[i][j], xx + i, yy + j);
    }
  }


  if (k == n - 1) {
    return solve(g);
  }

  auto [lx, rx] = get_bounds(xx, k + 1, n);
  auto [ly, ry] = get_bounds(yy, k + 1, n);

  std::string res(100, '0');
  for (int i = lx; i < rx; i++) {
    for (int j = ly; j < ry; j++) {
      int u = i - lx;
      int v = j - ly;
      res[u * (ry - ly) + v] = g[i][j];
    }
  }

  return res;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11