Submission #1063837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063837		kunzaZa183	Mars (APIO22_mars)	C++17	54 / 100	394 ms	4680 KiB

mars

#include "mars.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <utility>
using namespace std;

string process(vector<vector<string>> a, int x, int y, int k, int n) {

  auto helper = [&](int x, int y, int k) {
    vector<pair<int, int>> vpii;
    int dimens = n - k * 2;
    int each = n / dimens;
    int last = n % dimens;

    vector<int> vi(dimens, each);
    for (int i = 0; i < last; i++)
      vi[i]++;

    vector<int> coord(1, 0);
    for (int i = 0; i < vi.size() - 1; i++)
      coord.push_back(coord.back() + vi[i]);

    for (int i = coord[x]; i < coord[x] + vi[x]; i++)
      for (int j = coord[y]; j < coord[y] + vi[y]; j++)
        vpii.emplace_back(i, j);

    return vpii;
  };

  n *= 2;
  n++;

  vector<pair<int, int>> expect[3][3];

  map<pair<int, int>, int> mpiii;

  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++) {
      expect[i][j] = helper(x + i, y + j, k);
      for (int k = 0; k < expect[i][j].size(); k++)
        mpiii[expect[i][j][k]] = a[i][j][k] - '0';
    }

  if (k == (n - 1) / 2 - 1) {
    vector<vector<int>> vvi(n, vector<int>(n));
    vector<vector<int>> compo(n, vector<int>(n, -1));
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        vvi[i][j] = mpiii[make_pair(i, j)];
      }

    auto inr = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; };

    const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    function<void(int, int, int)> dfs = [&](int curx, int cury, int num) {
      compo[curx][cury] = num;
      for (int i = 0; i < 4; i++)
        if (inr(curx + dx[i], cury + dy[i])) {
          if (compo[curx + dx[i]][cury + dy[i]] == -1 &&
              vvi[curx + dx[i]][cury + dy[i]] == 1) {
            dfs(curx + dx[i], cury + dy[i], num);
          }
        }
    };

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

    int curval = 0;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) {
        if (compo[i][j] == -1 && vvi[i][j] == 1) {
          dfs(i, j, curval++);
        }
      }

    string s = bitset<100>(curval).to_string();
    reverse(s.begin(), s.end());
    return s;
  }

  vector<pair<int, int>> ans;

  ans = helper(x, y, k + 1);

  string s(100, '0');
  for (int i = 0; i < ans.size(); i++)
    s[i] = mpiii[ans[i]] + '0';

  return s;
}

Compilation message (stderr)

mars.cpp: In lambda function:
mars.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < vi.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       for (int k = 0; k < expect[i][j].size(); k++)
      |                       ~~^~~~~~~~~~~~~~~~~~~~~
mars.cpp:91:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for (int i = 0; i < ans.size(); i++)
      |                   ~~^~~~~~~~~~~~

• 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