Submission #668729

#	Time	Username	Problem	Language	Result	Execution time	Memory
668729		kenken714	Mars (APIO22_mars)	C++17	21 / 100	57 ms	2700 KiB

mars

#include "mars.h"
#include<vector>
#include<string>
#include<queue>
#include<iostream>
#include<cstdio>
using namespace std;

inline void subf(int y,int x,char a,int n,vector<vector<int>>& m) {
  if(0 <= y && y <= n && 0 <= x && x <= n)m[y][x] = (a=='0'?0:1);
}

int par(int x,vector<int>& p) {
  if(p[x] == x)return x;
  else return p[x] = par(p[x],p);
}

string solve(vector<vector<int>>& m,int n) {
  string res = string(100 ,'0');
  
  int C = n*n;
  vector<int> p(C);
  for(int ii=0;ii<C;ii++)p[ii] = ii;
  for(int y=1;y<n;y++)for(int x=0;x<n;x++) {
    if(m[y][x] && m[y-1][x]) {
      p[par(y*n+x,p)] = par((y-1)*n+x,p);
    }
  }
  for(int y=0;y<n;y++)for(int x=1;x<n;x++) {
    if(m[y][x] && m[y][x-1]) {
      p[par(y*n+x,p)] = par(y*n+x-1,p);
    }
  }
  vector<int> cnt(C,0);
  for(int y=0;y<n;y++)for(int x=0;x<n;x++)if(m[y][x])cnt[par(y*n+x,p)]++;
  int ans = 0;
  for(int ii=0;ii<C;ii++)if(cnt[ii])ans++;
  queue<int> resq;
  while(ans) {
    resq.push(ans&1);
    ans /= 2;
  }
  for(int ii=0;!resq.empty();ii++) {
    res[ii] = '0'+resq.front();
    resq.pop();
  }
  return res;
}

std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
  int s = 2*n+1;
  string res = string(100 ,'0');
  
  if(n == 1) {
    vector<vector<int>> m(3,vector<int>(3));
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y][x] = (a[y][x][0] == '0'?0:1);
    res = solve(m,3);
  }
  else if(k == 0) {
    for(int ii=0;ii<3;ii++)for(int jj=0;jj<3;jj++)res[ii*3+jj] = a[ii][jj][0];
  }
  else if(n == 2) {
    vector<vector<int>> m(5,vector<int>(5));
    for(int y=0;y<2;y++)for(int x=0;x<2;x++)m[y][x] = (a[0][0][y*3+x] == '0'?0:1);
    for(int y=0;y<2;y++)for(int x=0;x<3;x++)m[y][2+x] = (a[0][2][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<2;x++)m[2+y][x] = (a[2][0][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[2+y][2+x] = (a[2][2][y*3+x] == '0'?0:1);
    res = solve(m,5);
  }
  else if(n == 3) {
    if(k == 1) {
      if(i < 2 && j == 2)res = a[0][2];
      else if(i == 2 && j < 2)res = a[2][0];
      else if(i == 2 && j == 2)res = a[2][2];
      else res = a[0][0];
    }
    else {
      vector<vector<int>> m(7,vector<int>(7));
      for(int y=0;y<1;y++)for(int x=0;x<1;x++)m[y][x] = (a[0][0][y*3+x] == '0'?0:1);
      for(int y=0;y<1;y++)for(int x=0;x<3;x++)m[y][x+1] = (a[0][1][y*3+x] == '0'?0:1);
      for(int y=0;y<1;y++)for(int x=0;x<3;x++)m[y][x+4] = (a[0][2][y*3+x] == '0'?0:1);
      for(int y=0;y<3;y++)for(int x=0;x<1;x++)m[y+1][x] = (a[1][0][y*3+x] == '0'?0:1);
      for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+1][x+1] = (a[1][1][y*3+x] == '0'?0:1);
      for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+1][x+4] = (a[1][2][y*3+x] == '0'?0:1);
      for(int y=0;y<3;y++)for(int x=0;x<1;x++)m[y+4][x] = (a[2][0][y*3+x] == '0'?0:1);
      for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+4][x+1] = (a[2][1][y*3+x] == '0'?0:1);
      for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+4][x+4] = (a[2][2][y*3+x] == '0'?0:1);
      res = solve(m,7);
    }
  }
  else if(k == 1) {
    int y = -1,x = -1;
    if(i < s%9) {
      if(i == 0)y = 0;
      else if(i == 2)y = 1;
      else if(i == 4)y = 2;
    }
    else {
      if((s-i)%9 == 0)y = 0;
      else if((s-i)%9 == 7)y = 1;
      else if((s-i)%9 == 5)y = 2;
    }
    if(j < s%9) {
      if(j == 0)x = 0;
      else if(j == 2)x = 1;
      else if(j == 4)x = 2;
    }
    else {
      if((s-j)%9 == 0)x = 0;
      else if((s-j)%9 == 7)x = 1;
      else if((s-j)%9 == 5)x = 2;
    }
    if(y >= 0 && x >= 0)res = a[y][x];
  }
  else if(k == 2) {
    int y = -1,x = -1;
    if(i < s%9) {
      if(i == 0)y = 0;
      else if(i == 1)y = 1;
      else if(i == 2)y = 2;
    }
    else {
      if((s-i)%9 == 0)y = 0;
      else if((s-i)%9 == 8)y = 1;
      else if((s-i)%9 == 7)y = 2;
    }
    if(j < s%9) {
      if(j == 0)x = 0;
      else if(j == 1)x = 1;
      else if(j == 2)x = 2;
    }
    else {
      if((s-j)%9 == 0)x = 0;
      else if((s-j)%9 == 8)x = 1;
      else if((s-j)%9 == 7)x = 2;
    }
    if(y >= 0 && x >= 0)res = a[y][x];
  }
  else if(n == 4) {
    vector<vector<int>> m(9,vector<int>(9));
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y][x] = (a[0][0][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y][x+3] = (a[0][1][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y][x+6] = (a[0][2][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+3][x] = (a[1][0][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+3][x+3] = (a[1][1][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+3][x+6] = (a[1][2][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+6][x] = (a[2][0][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+6][x+3] = (a[2][1][y*3+x] == '0'?0:1);
    for(int y=0;y<3;y++)for(int x=0;x<3;x++)m[y+6][x+6] = (a[2][2][y*3+x] == '0'?0:1);
    res = solve(m,9);
  }
  else if(k == 3) {
    for(int ii=0;ii<3;ii++)for(int jj=0;jj<3;jj++)for(int kk=0;kk<3;kk++)for(int ll=0;ll<3;ll++) {
      res[ii*27+jj*9+kk*3+ll] = a[ii][kk][jj*3+ll];
    }
  }
  else if(n == 5) {
    vector<vector<int>> m(11,vector<int>(11));
    for(int y=0;y<2;y++)for(int x=0;x<2;x++)m[y][x] = (a[0][0][y*9+x] == '0'?0:1);
    for(int y=0;y<2;y++)for(int x=0;x<9;x++)m[y][x+2] = (a[0][2][y*9+x] == '0'?0:1);
    for(int y=0;y<9;y++)for(int x=0;x<2;x++)m[y+2][x] = (a[2][0][y*9+x] == '0'?0:1);
    for(int y=0;y<9;y++)for(int x=0;x<9;x++)m[y+2][x+2] = (a[2][2][y*9+x] == '0'?0:1);
    res = solve(m,11);
  }
  else if(n < 9 && k == n-1) {
    vector<vector<int>> m(n+n+1,vector<int>(n+n+1));
    for(int y=0;y<n+n-8;y++)for(int x=0;x<n+n-8;x++)m[y][x] = (a[0][0][y*9+x] == '0'?0:1);
    for(int y=0;y<n+n-8;y++)for(int x=0;x<9;x++)m[y][x+n+n-8] = (a[0][2][y*9+x] == '0'?0:1);
    for(int y=0;y<9;y++)for(int x=0;x<n+n-8;x++)m[y+n+n-8][x] = (a[2][0][y*9+x] == '0'?0:1);
    for(int y=0;y<9;y++)for(int x=0;x<9;x++)m[y+n+n-8][x+n+n-8] = (a[2][2][y*9+x] == '0'?0:1);
    res = solve(m,n+n+1);
  }
  else if((k*2+s%9-1)/8*9 < 2*n+1) {
    int c = (k*2+s%9-1)/8,y = 0,x = 0;
    if(i == c) {
      if((k*2+s%9+1)/8 > c && (s%9-1)%2 > 0)y = 1;
      else y = 2;
    }
    if(j == c) {
      if((k*2+s%9+1)/8 > c && (s%9-1)%2 > 0)x = 1;
      else x = 2;
    }
    if(i > c)y = 2;
    if(j > c)x = 2;
    res = a[y][x];
  }
  else if(k < n-1) {
    if(i == 0 && j == 0) {
      vector<vector<int>> m(n+1,vector<int>(n+1));
      for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<s%9;jj++)m[ii][jj] = (a[0][0][ii*9+jj]=='0'?0:1);
      for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)if(s%9+jj <= n)m[ii][s%9+jj] = (a[0][1][ii*9+jj]=='0'?0:1);
      for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)if(s%9+9+jj <= n)m[ii][s%9+9+jj] = (a[0][2][ii*9+jj]=='0'?0:1);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)if(s%9+ii <= n)m[s%9+ii][jj] = (a[1][0][ii*9+jj]=='0'?0:1);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)if(s%9+ii <= n && s%9+jj <= n)m[s%9+ii][s%9+jj] = (a[1][1][ii*9+jj]=='0'?0:1);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)if(s%9+ii <= n && s%9+9+jj <= n)m[s%9+ii][s%9+9+jj] = (a[1][2][ii*9+jj]=='0'?0:1);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)if(s%9+9+ii <= n)m[s%9+9+ii][jj] = (a[2][0][ii*9+jj]=='0'?0:1);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)if(s%9+9+ii <= n && s%9+jj <= n)m[s%9+9+ii][s%9+jj] = (a[2][1][ii*9+jj]=='0'?0:1);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)if(s%9+9+ii <= n && s%9+9+jj <= n)m[s%9+9+ii][s%9+9+jj] = (a[2][2][ii*9+jj]=='0'?0:1);
      int C = (n+1)*(n+1);
      vector<int> p(C);
      for(int ii=0;ii<C;ii++)p[ii] = ii;
      for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
        if(m[y][x] && m[y+1][x]) {
          p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
        }
      }
      for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
        if(m[y][x] && m[y][x+1]) {
          p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
        }
      }
      vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
      for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
      for(int y=0;y<n;y++)if(m[y][n])cntv[p[y*(n+1)+n]]++;
      for(int x=0;x<n;x++)if(m[n][x])cnth[p[n*(n+1)+x]]++;
      int ans = 0;
      for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
      queue<int> resq;
      resq.push(m[n][n]);
      int prev = -1;
      if(m[n][n])prev = p[C-1];
      for(int y=n-1;y>=0;y--) {
        if(m[y][n]) {
          if(prev == p[y*(n+1)+n]) {
            resq.push(0);
            resq.push(1);
          }
          else {
            prev = p[y*(n+1)+n];
            resq.push(1);
            resq.push(cnth[p[y*(n+1)+n]]?1:0);
          }
        }
        else {
          resq.push(0);
          resq.push(0);
        }
      }
      prev = -1;
      if(m[n][n])prev = p[C-1];
      for(int x=n-1;x>=0;x--) {
        if(m[n][x]) {
          if(prev == p[n*(n+1)+x]) {
            resq.push(0);
            resq.push(1);
          }
          else {
            prev = p[n*(n+1)+x];
            resq.push(1);
            resq.push(cntv[p[n*(n+1)+x]]?1:0);
          }
        }
        else {
          resq.push(0);
          resq.push(0);
        }
      }
      while(ans) {
        resq.push(ans&1);
        ans /= 2;
      }
      for(int ii=0;!resq.empty();ii++) {
        res[ii] = '0'+resq.front();
        resq.pop();
      }
    }
    else if(n > 17) {
      if(i == 0 && j == 2) {
        vector<vector<int>> m(n+1,vector<int>(n+1));
        for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+jj-n,a[0][0][ii*9+jj],n,m);
        for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+9+jj-n,a[0][1][ii*9+jj],n,m);
        for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+9+9+jj-n,a[0][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+jj-n,a[1][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+9+jj-n,a[1][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+9+9+jj-n,a[1][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+jj-n,a[2][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+9+jj-n,a[2][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+9+9+jj-n,a[2][2][ii*9+jj],n,m);
        int C = (n+1)*(n+1);
        vector<int> p(C);
        for(int ii=0;ii<C;ii++)p[ii] = ii;
        for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
          if(m[y][x] && m[y+1][x]) {
            p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
          }
        }
        for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
          if(m[y][x] && m[y][x+1]) {
            p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
          }
        }
        vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
        for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
        for(int y=0;y<n;y++)if(m[y][0])cntv[p[y*(n+1)]]++;
        for(int x=0;x<n;x++)if(m[n][x])cnth[p[n*(n+1)+x]]++;
        int ans = 0;
        for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
        queue<int> resq;
        resq.push(m[n][0]);
        int prev = -1;
        if(m[n][0])prev = p[n*(n+1)];
        for(int y=n-1;y>=0;y--) {
          if(m[y][0]) {
            if(prev == p[y*(n+1)+0]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[y*(n+1)+0];
              resq.push(1);
              resq.push(cnth[p[y*(n+1)+0]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        prev = -1;
        if(m[n][0])prev = p[n*(n+1)];
        for(int x=1;x<=n;x++) {
          if(m[n][x]) {
            if(prev == p[n*(n+1)+x]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[n*(n+1)+x];
              resq.push(1);
              resq.push(cntv[p[n*(n+1)+x]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        while(ans) {
          resq.push(ans&1);
          ans /= 2;
        }
        for(int ii=0;!resq.empty();ii++) {
          res[ii] = '0'+resq.front();
          resq.pop();
        }
      }
      else if(i == 2 && j == 2) {
        vector<vector<int>> m(n+1,vector<int>(n+1));
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+jj-n,a[0][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+9+jj-n,a[0][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+9+9+jj-n,a[0][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+jj-n,a[1][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+9+jj-n,a[1][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+9+9+jj-n,a[1][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+9+jj-n,a[2][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+9+9+jj-n,a[2][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+9+9+9+jj-n,a[2][2][ii*9+jj],n,m);
        int C = (n+1)*(n+1);
        vector<int> p(C);
        for(int ii=0;ii<C;ii++)p[ii] = ii;
        for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
          if(m[y][x] && m[y+1][x]) {
            p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
          }
        }
        for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
          if(m[y][x] && m[y][x+1]) {
            p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
          }
        }
        vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
        for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
        for(int y=0;y<n;y++)if(m[y][0])cntv[p[y*(n+1)]]++;
        for(int x=0;x<n;x++)if(m[0][x])cnth[p[x]]++;
        int ans = 0;
        for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
        queue<int> resq;
        resq.push(m[0][0]);
        int prev = -1;
        if(m[0][0])prev = p[0];
        for(int y=1;y<=n;y++) {
          if(m[y][0]) {
            if(prev == p[y*(n+1)]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[y*(n+1)];
              resq.push(1);
              resq.push(cnth[p[y*(n+1)]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        prev = -1;
        if(m[0][0])prev = p[0];
        for(int x=1;x<=n;x++) {
          if(m[0][x]) {
            if(prev == p[x]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[x];
              resq.push(1);
              resq.push(cntv[p[x]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        while(ans) {
          resq.push(ans&1);
          ans /= 2;
        }
        for(int ii=0;!resq.empty();ii++) {
          res[ii] = '0'+resq.front();
          resq.pop();
        }
      }
      else if(i == 2 && j == 0) {
        vector<vector<int>> m(n+1,vector<int>(n+1));
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+ii-n,jj,a[0][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+jj,a[0][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+jj,a[0][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+9+ii-n,jj,a[1][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+jj,a[1][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+jj,a[1][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+9+9+ii-n,jj,a[2][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+jj,a[2][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+9+ii-n,s%9+9+jj,a[2][2][ii*9+jj],n,m);
        int C = (n+1)*(n+1);
        vector<int> p(C);
        for(int ii=0;ii<C;ii++)p[ii] = ii;
        for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
          if(m[y][x] && m[y+1][x]) {
            p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
          }
        }
        for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
          if(m[y][x] && m[y][x+1]) {
            p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
          }
        }
        vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
        for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
        for(int y=0;y<n;y++)if(m[y][n])cntv[p[y*(n+1)+n]]++;
        for(int x=0;x<n;x++)if(m[0][x])cnth[p[x]]++;
        int ans = 0;
        for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
        queue<int> resq;
        resq.push(m[0][n]);
        int prev = -1;
        if(m[0][n])prev = p[n];
        for(int y=1;y<=n;y++) {
          if(m[y][n]) {
            if(prev == p[y*(n+1)+n]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[y*(n+1)+n];
              resq.push(1);
              resq.push(cnth[p[y*(n+1)+n]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        prev = -1;
        if(m[0][0])prev = p[0];
        for(int x=n-1;x>=0;x--) {
          if(m[0][x]) {
            if(prev == p[x]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[x];
              resq.push(1);
              resq.push(cntv[p[x]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        while(ans) {
          resq.push(ans&1);
          ans /= 2;
        }
        for(int ii=0;!resq.empty();ii++) {
          res[ii] = '0'+resq.front();
          resq.pop();
        }
      }
    }
    else {
      if(i == 0 && j == 1) {
        vector<vector<int>> m(n+1,vector<int>(n+1));
        for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+jj-n,a[0][0][ii*9+jj],n,m);
        for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+jj-n,a[0][1][ii*9+jj],n,m);
        for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+9+jj-n,a[0][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+jj-n,a[1][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+jj-n,a[1][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+9+jj-n,a[1][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+jj-n,a[2][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+jj-n,a[2][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+9+jj-n,a[2][2][ii*9+jj],n,m);
        int C = (n+1)*(n+1);
        vector<int> p(C);
        for(int ii=0;ii<C;ii++)p[ii] = ii;
        for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
          if(m[y][x] && m[y+1][x]) {
            p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
          }
        }
        for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
          if(m[y][x] && m[y][x+1]) {
            p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
          }
        }
        vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
        for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
        for(int y=0;y<n;y++)if(m[y][0])cntv[p[y*(n+1)]]++;
        for(int x=0;x<n;x++)if(m[n][x])cnth[p[n*(n+1)+x]]++;
        int ans = 0;
        for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
        queue<int> resq;
        resq.push(m[n][0]);
        int prev = -1;
        if(m[n][0])prev = p[n*(n+1)];
        for(int y=n-1;y>=0;y--) {
          if(m[y][0]) {
            if(prev == p[y*(n+1)+0]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[y*(n+1)+0];
              resq.push(1);
              resq.push(cnth[p[y*(n+1)+0]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        prev = -1;
        if(m[n][0])prev = p[n*(n+1)];
        for(int x=1;x<=n;x++) {
          if(m[n][x]) {
            if(prev == p[n*(n+1)+x]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[n*(n+1)+x];
              resq.push(1);
              resq.push(cntv[p[n*(n+1)+x]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        while(ans) {
          resq.push(ans&1);
          ans /= 2;
        }
        for(int ii=0;!resq.empty();ii++) {
          res[ii] = '0'+resq.front();
          resq.pop();
        }
      }
      else if(i == 1 && j == 1) {
        vector<vector<int>> m(n+1,vector<int>(n+1));
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+jj-n,a[0][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+9+jj-n,a[0][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+9+9+jj-n,a[0][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+jj-n,a[1][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+jj-n,a[1][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+9+jj-n,a[1][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+jj-n,a[2][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+jj-n,a[2][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+9+jj-n,a[2][2][ii*9+jj],n,m);
        int C = (n+1)*(n+1);
        vector<int> p(C);
        for(int ii=0;ii<C;ii++)p[ii] = ii;
        for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
          if(m[y][x] && m[y+1][x]) {
            p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
          }
        }
        for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
          if(m[y][x] && m[y][x+1]) {
            p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
          }
        }
        vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
        for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
        for(int y=0;y<n;y++)if(m[y][0])cntv[p[y*(n+1)]]++;
        for(int x=0;x<n;x++)if(m[0][x])cnth[p[x]]++;
        int ans = 0;
        for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
        queue<int> resq;
        resq.push(m[0][0]);
        int prev = -1;
        if(m[0][0])prev = p[0];
        for(int y=1;y<=n;y++) {
          if(m[y][0]) {
            if(prev == p[y*(n+1)]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[y*(n+1)];
              resq.push(1);
              resq.push(cnth[p[y*(n+1)]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        prev = -1;
        if(m[0][0])prev = p[0];
        for(int x=1;x<=n;x++) {
          if(m[0][x]) {
            if(prev == p[x]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[x];
              resq.push(1);
              resq.push(cntv[p[x]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        while(ans) {
          resq.push(ans&1);
          ans /= 2;
        }
        for(int ii=0;!resq.empty();ii++) {
          res[ii] = '0'+resq.front();
          resq.pop();
        }
      }
      else if(i == 1 && j == 0) {
        vector<vector<int>> m(n+1,vector<int>(n+1));
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+ii-n,jj,a[0][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+jj,a[0][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii-n,s%9+9+jj,a[0][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+ii-n,jj,a[1][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+jj,a[1][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii-n,s%9+9+jj,a[1][2][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+9+ii-n,jj,a[2][0][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+jj,a[2][1][ii*9+jj],n,m);
        for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+9+ii-n,s%9+9+jj,a[2][2][ii*9+jj],n,m);
        int C = (n+1)*(n+1);
        vector<int> p(C);
        for(int ii=0;ii<C;ii++)p[ii] = ii;
        for(int y=0;y<n;y++)for(int x=0;x<=n;x++) {
          if(m[y][x] && m[y+1][x]) {
            p[par(y*(n+1)+x,p)] = par((y+1)*(n+1)+x,p);
          }
        }
        for(int y=0;y<=n;y++)for(int x=0;x<n;x++) {
          if(m[y][x] && m[y][x+1]) {
            p[par(y*(n+1)+x,p)] = par(y*(n+1)+x+1,p);
          }
        }
        vector<int> cnt(C,0),cntv(C,0),cnth(C,0);
        for(int y=0;y<=n;y++)for(int x=0;x<=n;x++)if(m[y][x])cnt[par(y*(n+1)+x,p)]++;
        for(int y=0;y<n;y++)if(m[y][n])cntv[p[y*(n+1)+n]]++;
        for(int x=0;x<n;x++)if(m[0][x])cnth[p[x]]++;
        int ans = 0;
        for(int ii=0;ii<C;ii++)if(cnt[ii] > 0 && cntv[ii] == 0 && cnth[ii] == 0)ans++;
        queue<int> resq;
        resq.push(m[0][n]);
        int prev = -1;
        if(m[0][n])prev = p[n];
        for(int y=1;y<=n;y++) {
          if(m[y][n]) {
            if(prev == p[y*(n+1)+n]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[y*(n+1)+n];
              resq.push(1);
              resq.push(cnth[p[y*(n+1)+n]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        prev = -1;
        if(m[0][0])prev = p[0];
        for(int x=n-1;x>=0;x--) {
          if(m[0][x]) {
            if(prev == p[x]) {
              resq.push(0);
              resq.push(1);
            }
            else {
              prev = p[x];
              resq.push(1);
              resq.push(cntv[p[x]]?1:0);
            }
          }
          else {
            resq.push(0);
            resq.push(0);
          }
        }
        while(ans) {
          resq.push(ans&1);
          ans /= 2;
        }
        for(int ii=0;!resq.empty();ii++) {
          res[ii] = '0'+resq.front();
          resq.pop();
        }
      }
    }
  }
  else {
    // last
    if(true) {
      vector<vector<int>> m(n+n+1,vector<int>(n+n+1));
      for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<s%9;jj++)subf(ii,jj,a[0][0][ii*9+jj],n+n,m);
      for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+jj,a[0][1][ii*9+jj],n+n,m);
      for(int ii=0;ii<s%9;ii++)for(int jj=0;jj<9;jj++)subf(ii,s%9+9+jj,a[0][2][ii*9+jj],n+n,m);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+ii,jj,a[1][0][ii*9+jj],n+n,m);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+jj,a[1][1][ii*9+jj],n+n,m);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+ii,s%9+9+jj,a[1][2][ii*9+jj],n+n,m);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<s%9;jj++)subf(s%9+9+ii,jj,a[2][0][ii*9+jj],n+n,m);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+jj,a[2][1][ii*9+jj],n+n,m);
      for(int ii=0;ii<9;ii++)for(int jj=0;jj<9;jj++)subf(s%9+9+ii,s%9+9+jj,a[2][2][ii*9+jj],n+n,m);
      int C = (n+n+1)*(n+n+1);
      vector<int> p(C);
      for(int ii=0;ii<C;ii++)p[ii] = ii;
      for(int y=0;y<n+n;y++)for(int x=0;x<=n+n;x++) {
        if(m[y][x] && m[y+1][x]) {
          p[par(y*(n+n+1)+x,p)] = par((y+1)*(n+n+1)+x,p);
        }
      }
      for(int y=0;y<=n+n;y++)for(int x=0;x<n+n;x++) {
        if(m[y][x] && m[y][x+1]) {
          p[par(y*(n+n+1)+x,p)] = par(y*(n+n+1)+x+1,p);
        }
      }
      vector<int> cnt(C,0);
      for(int y=0;y<=n+n;y++)for(int x=0;x<=n+n;x++)if(m[y][x])cnt[par(y*(n+n+1)+x,p)]++;
      int ans = 0;
      for(int ii=0;ii<C;ii++)if(cnt[ii])ans++;
      queue<int> resq;
      while(ans) {
        resq.push(ans&1);
        ans /= 2;
      }
      for(int ii=0;!resq.empty();ii++) {
        res[ii] = '0'+resq.front();
        resq.pop();
      }
    }
    else {
    }
  }
  
	return res;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 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