Submission #1063965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063965		sleepntsheep	Mars (APIO22_mars)	C++17	14 / 100	14 ms	3200 KiB

mars

#include "mars.h"
#include <cassert>
#include <iostream>
#include <queue>

using namespace std;

int map(int i, int j, int n) {
  assert(i<n and j<n);
  return 1 + i * n + j;
}

string process(vector <vector<string>> a, int i, int j, int k, int n)
{
  string tl = a[0][0];
  for (int ii = i; ii < i + 3; ++ii) {
    for (int jj = j; jj < j + 3; ++jj) {
      for(int k=1;k<100;++k)if(a[ii-i][jj-j][k]=='1')tl[k]='1';
      if (a[ii-i][jj-j][0]=='1') tl[map(ii,jj,2*n+1)] = '1';
    }
  }

  if (k == n - 1) {
    n=2*n+1;

    int vis[100] {},cmp{};
    tl.erase(tl.begin());
    queue<int> q;
    for (int i=0;i<n*n;++i){
      if(not vis[i] and tl[i]=='1'){
        ++cmp;
        q.push(i),vis[i]=1;
        while(q.size()){
          int u=q.front();q.pop();
          auto nq=[&](int v){if(v>=0 and v<n*n and not vis[v] and tl[v]=='1')vis[v]=1,q.push(v);};
          if(u%n)nq(u-1);
          if((u+1)%n)nq(u+1);
          nq(u-n),nq(u+n);
        }
      }
    }

    string out(100,'0');
    for(int j=0;j<20;++j)if((cmp&(1<<j)))out[j]='1';
    return out;
  }
  return tl;
}

• 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