Submission #594823

#	Time	Username	Problem	Language	Result	Execution time	Memory
594823		lunchbox	Mars (APIO22_mars)	C++17	14 / 100	19 ms	2248 KiB

mars

#include <bits/stdc++.h>
using namespace std;

struct dsu {
  vector<int> ds;

  dsu() {}
  dsu(int n) {
    ds.assign(n, -1);
  }
  const int& operator[](int i) {
    return ds[i];
  }
  int find(int i) {
    return ds[i] < 0 ? i : ds[i] = find(ds[i]);
  }
  int size(int i) {
    return -ds[find(i)];
  }
  bool same(int i, int j) {
    return find(i) == find(j);
  }
  bool join(int i, int j) {
    i = find(i), j = find(j);
    if (i == j)
      return false;
    if (ds[i] > ds[j])
      swap(i, j);
    ds[i] += ds[j], ds[j] = i;
    return true;
  }
};

string process(vector<vector<string>> ss, int i, int j, int k, int n) {
  int n_ = (k + 1) * 2 + 1;
  string s(100, '0');
  for (int x1 = 0; x1 < 3; x1++)
    for (int y1 = 0; y1 < 3; y1++)
        for (int x2 = 0; x2 < n_ - 2; x2++)
          for (int y2 = 0; y2 < n_ - 2; y2++)
            s[(x1 + x2) * n_ + (y1 + y2)] = ss[x1][y1][x2 * (n_ - 2) + y2];
  if (k < n - 1)
    return s;
  else {
    dsu ds(n_ * n_);
    int m = 0;
    for (int x = 0; x < n_; x++)
      for (int y = 0; y < n_; y++)
        if (s[x * n_ + y] == '1') {
          if (x > 0 && s[(x - 1) * n_ + y] == '1')
            ds.join(x * n_ + y, (x - 1) * n_ + y);
          if (y > 0 && s[x * n_ + (y - 1)] == '1')
            ds.join(x * n_ + y, x * n_ + (y - 1));
        }
    for (int i = 0; i < n_ * n_; i++)
      if (ds[i] < 0 && s[i] == '1')
        m++;
    string t(100, '0');
    for (int b = 0; b < 10; b++)
      t[b] = '0' + (m >> b & 1);
    return t;
  }
}

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