Submission #595419

#	Time	Username	Problem	Language	Result	Execution time	Memory
595419		lunchbox	Mars (APIO22_mars)	C++17	100 / 100	1277 ms	4820 KiB

mars

#ifndef LOCAL
  #include "mars.h"
#endif
#include <bits/stdc++.h>
using namespace std;
 
struct dsu {
  vector<int> ds;
  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 fill(string s) {
  while (s.size() < 100)
    s += "0";
  return s;
}
 
string process(vector<vector<string>> ss, int i, int j, int k, int n) {
  int b = 2 * (n - k - 1), n_ = (k + 1) * 2 + 1;
  if (i < b && j < b)
    return ss[0][0];
  else if (i == b && j != b) {
    swap(ss[0][1], ss[1][0]);
    swap(ss[0][2], ss[2][0]);
    swap(ss[1][2], ss[2][1]);
    string s;
    for (int i1 = 0; i1 < 2; i1++) {
      for (int j1 = 0; j1 < 2; j1++)
        s += ss[i1][j1][0];
      for (int j1 = 0; j1 < n_ - 2; j1++)
        s += ss[i1][2][j1];
    }
    return fill(s);
  } else if (i != b && j == b) {
    string s;
    for (int i1 = 0; i1 < 2; i1++) {
      for (int j1 = 0; j1 < 2; j1++)
        s += ss[i1][j1][0];
      for (int j1 = 0; j1 < n_ - 2; j1++)
        s += ss[i1][2][j1];
    }
    return fill(s);
  } else {
    if (k == 0) {
      dsu ds(n_ * n_);
      for (int i1 = 0; i1 < n_; i1++)
        for (int j1 = 0; j1 < n_; j1++)
          if (ss[i1][j1][0] == '1') {
            if (i1 > 0 && ss[i1 - 1][j1][0] == '1')
              ds.join(i1 * n_ + j1, (i1 - 1) * n_ + j1);
            if (j1 > 0 && ss[i1][j1 - 1][0] == '1')
              ds.join(i1 * n_ + j1, i1 * n_ + (j1 - 1));
          }
      int c = 0;
      for (int i1 = 0; i1 < n_; i1++)
        for (int j1 = 0; j1 < n_; j1++)
          if (ss[i1][j1][0] == '1' && ds[i1 * n_ + j1] < 0)
            c++;
      if (n == 1) {
        string s(100, '0');
        for (int x = 0; x < 10; x++)
          s[x] = '0' + (c >> x & 1);
        return s;
      }
      vector<int> ii;
      for (int i1 = 2; i1 >= 0; i1--)
        if (ss[0][i1][0] == '1' && (i1 == 2 || ss[0][i1 + 1][0] == '0'))
          ii.push_back(ds.find(0 * n_ + i1));
      for (int i1 = 1; i1 < 3; i1++)
        if (ss[i1][0][0] == '1' && ss[i1 - 1][0][0] == '0')
          ii.push_back(ds.find(i1 * n_ + 0));
      vector<int> stack, marked(n_ * n_);
      string s(100, '0');
      for (int i1 = 0; i1 < (int) ii.size(); i1++)
        if (!stack.empty() && marked[ii[i1]]) {
          while (ii[stack.back()] != ii[i1]) {
            s[stack.back() << 1 | 1] = '1';
            stack.pop_back();
          }
          stack.pop_back();
          stack.push_back(i1);
        } else {
          s[i1 << 1 | 0] = '1';
          marked[ii[i1]] = 1, stack.push_back(i1);
        }
      while (!stack.empty()) {
        s[stack.back() << 1 | 1] = '1';
        stack.pop_back();
      }
      for (int x = 0; x < 10; x++)
        s[90 + x] = '0' + (c >> x & 1);
      return s;
    } else {
      vector<vector<int>> gr(n_, vector<int>(n_, 0));
      for (int i1 = 0; i1 < 2; i1++)
        for (int j1 = 0; j1 < 2; j1++)
          gr[i1][j1] = ss[i1][j1][0] - '0';
      for (int i1 = 0; i1 < n_ - 2; i1++)
        for (int j1 = 0; j1 < 2; j1++) {
          gr[j1][i1 + 2] = ss[0][2][j1 * (n_ - 2) + i1] - '0';
          gr[i1 + 2][j1] = ss[2][0][j1 * (n_ - 2) + i1] - '0';
        }
      for (int i1 = 0; i1 < n_ - 2; i1++) {
        gr[2][i1 + 2] = ss[1][2][n_ - 2 + i1] - '0';
        gr[i1 + 2][2] = ss[2][1][n_ - 2 + i1] - '0';
      }
      int c = 0;
      for (int x = 0; x < 10; x++)
        if (ss[2][2][90 + x] == '1')
          c |= 1 << x;
      for (int i1 = 0; i1 < n_; i1++)
        for (int j1 = 0; j1 < 2; j1++)
          c += gr[i1][j1] + gr[j1][i1];
      c -= gr[0][0];
      c -= gr[0][1];
      c -= gr[1][0];
      c -= gr[1][1];
      dsu ds(n_ * n_);
      for (int i1 = 0; i1 < n_; i1++) {
        if (gr[0][i1] && gr[1][i1] && ds.join(0 * n_ + i1, 1 * n_ + i1))
          c--;
        if (gr[i1][0] && gr[i1][1] && ds.join(i1 * n_ + 0, i1 * n_ + 1))
          c--;
        for (int j1 = 0; j1 < 2; j1++) {
          if (i1 < n_ - 1 && gr[i1][j1] && gr[i1 + 1][j1] && ds.join(i1 * n_ + j1, (i1 + 1) * n_ + j1))
            c--;
          if (i1 < n_ - 1 && gr[j1][i1] && gr[j1][i1 + 1] && ds.join(j1 * n_ + i1, j1 * n_ + (i1 + 1)))
            c--;
        }
      }
      for (int i1 = n_ - 2; i1 >= 2; i1--)
        if (gr[2][i1] && gr[2][i1 + 1])
          ds.join(2 * n_ + i1, 2 * n_ + (i1 + 1));
      for (int i1 = 3; i1 < n_; i1++)
        if (gr[i1][2] && gr[i1 - 1][2])
          ds.join(i1 * n_ + 2, (i1 - 1) * n_ + 2);
      vector<int> ii;
      for (int i1 = n_ - 1; i1 >= 2; i1--)
        if (gr[2][i1] && (i1 == n_ - 1 || !gr[2][i1 + 1]))
          ii.push_back(ds.find(2 * n_ + i1));
      for (int i1 = 3; i1 < n_; i1++)
        if (gr[i1][2] && !gr[i1 - 1][2])
          ii.push_back(ds.find(i1 * n_ + 2));
      vector<int> stack, mark(ii.size());
      for (int i1 = 0; i1 < (int) ii.size(); i1++) {
        if (ss[2][2][i1 << 1 | 0] == '1')
          stack.push_back(i1);
        mark[i1] = stack.back();
        for (int j1 = 0; j1 < i1; j1++)
          if (mark[j1] == mark[i1])
            ds.join(ii[i1], ii[j1]);
        if (ss[2][2][i1 << 1 | 1] == '1')
          stack.pop_back();
      }
      for (int i1 = 2; i1 < n_; i1++) {
        if (gr[1][i1] && gr[2][i1] && ds.join(1 * n_ + i1, 2 * n_ + i1))
          c--;
        if (gr[i1][1] && gr[i1][2] && ds.join(i1 * n_ + 1, i1 * n_ + 2))
          c--;
      }
      ii.clear();
      for (int i1 = n_ - 1; i1 >= 0; i1--)
        if (gr[0][i1] && (i1 == n_ - 1 || !gr[0][i1 + 1]))
          ii.push_back(ds.find(0 * n_ + i1));
      for (int i1 = 1; i1 < n_; i1++)
        if (gr[i1][0] && !gr[i1 - 1][0])
          ii.push_back(ds.find(i1 * n_ + 0));
      vector<int> marked(n_ * n_);
      string s(100, '0');
      if (k == n - 1) {
        for (int x = 0; x < 10; x++)
          s[x] = '0' + (c >> x & 1);
        return s;
      }
      for (int i1 = 0; i1 < (int) ii.size(); i1++)
        if (!stack.empty() && marked[ii[i1]]) {
          while (ii[stack.back()] != ii[i1]) {
            s[stack.back() << 1 | 1] = '1';
            stack.pop_back();
          }
          stack.pop_back();
          stack.push_back(i1);
        } else {
          s[i1 << 1 | 0] = '1';
          marked[ii[i1]] = 1, stack.push_back(i1);
        }
      while (!stack.empty()) {
        s[stack.back() << 1 | 1] = '1';
        stack.pop_back();
      }
      for (int x = 0; x < 10; x++)
        s[90 + x] = '0' + (c >> x & 1);
      return s;
    }
  }
}

• 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: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11