Submission #718410

#	Time	Username	Problem	Language	Result	Execution time	Memory
718410		lam	Mars (APIO22_mars)	C++17	36 / 100	216 ms	3144 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
#define ff first
#define ss second
const int maxn = 110;
int n,m;
bool A[maxn][maxn];
bool dau[maxn][maxn];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

bool in(int x, int y)
{
    if (x<0||x>=m||y<0||y>=m) return 0;
    return A[x][y];
}

void dfs(int x, int y)
{
    dau[x][y]=1;
//    cerr<<"vis "<<x<<' '<<y<<endl;
    for (int c=0; c<4; c++)
    {
        int xx=x+dx[c];
        int yy=y+dy[c];
        if (in(xx,yy)&&!dau[xx][yy]) dfs(xx,yy);
    }
}

std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int N)
{
    n=N; m=2*n+1;
    map<ii,bool> mp;
    if (k!=n-1)
    {
        for (int i=0; i<3; i+=2)
            for (int j=0; j<3; j+=2)
        {
            int cnt=0;
            for (int i2=0; i2<=k; i2++)
                for (int j2=0; j2<=k; j2++)
                    mp[{i+i2*2,j+j2*2}] = (a[i][j][cnt++]=='1');
         }
        string S="";
        for (int i=0; i<=k+1; i++)
            for (int j=0; j<=k+1; j++)
                if (mp[{2*i,2*j}]==1) S+='1';
                else S+='0';
        while (S.length()<100) S+='0';
        return S;
    }
    for (int i=0; i<3; i++)
        for (int j=0; j<3; j++)
    {
        int cnt=0;
        for (int i2=0; i2<=k; i2++)
            for (int j2=0; j2<=k; j2++)
                mp[{i+i2*2,j+j2*2}] = (a[i][j][cnt++]=='1');
     }
     for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
        A[i][j] = mp[{i,j}];
//    for (int i=0; i<m; i++)
//    {
//        for (int j=0; j<m; j++)cerr<<A[i][j]<<' ';
//        cerr<<endl;
//    }
    int ans = 0;
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++) dau[i][j]=0;
    for (int i=0; i<m; i++)
        for (int j=0; j<m; j++)
        if (!dau[i][j]&&A[i][j]==1) dfs(i,j), ans++;
    string S="";
    while (ans>0)
    {
        if (ans&1) S+='1';
        else S+='0';
        ans/=2;
    }
    while (S.length()<100) S+='0';
    return S;
}

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