Submission #821322

#	Time	Username	Problem	Language	Result	Execution time	Memory
821322		Hanksburger	Mars (APIO22_mars)	C++17	54 / 100	278 ms	3804 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
string process(vector<vector<string> > a, int i, int j, int k, int n)
{
    int il0=(2*n+1)*  i  /(2*(n-k)+1)+1;
    int ir0=(2*n+1)*(i+1)/(2*(n-k)+1);
    int il1=(2*n+1)*(i+1)/(2*(n-k)+1)+1;
    int ir1=(2*n+1)*(i+2)/(2*(n-k)+1);
    int il2=(2*n+1)*(i+2)/(2*(n-k)+1)+1;
    int ir2=(2*n+1)*(i+3)/(2*(n-k)+1);
    
    int jl0=(2*n+1)*  j  /(2*(n-k)+1)+1;
    int jr0=(2*n+1)*(j+1)/(2*(n-k)+1);
    int jl1=(2*n+1)*(j+1)/(2*(n-k)+1)+1;
    int jr1=(2*n+1)*(j+2)/(2*(n-k)+1);
    int jl2=(2*n+1)*(j+2)/(2*(n-k)+1)+1;
    int jr2=(2*n+1)*(j+3)/(2*(n-k)+1);
    
    int iltarget=(2*n+1)*  i  /(2*(n-k-1)+1)+1;
    int irtarget=(2*n+1)*(i+1)/(2*(n-k-1)+1);
    
    int jltarget=(2*n+1)*  j  /(2*(n-k-1)+1)+1;
    int jrtarget=(2*n+1)*(j+1)/(2*(n-k-1)+1);

    char arr[45][45];
    for (int i=il0; i<=ir0; i++)
    {
        for (int j=jl0; j<=jr0; j++)
            arr[i][j]=a[0][0][(i-il0)*(jr0-jl0+1)+j-jl0];
        for (int j=jl1; j<=jr1; j++)
            arr[i][j]=a[0][1][(i-il0)*(jr1-jl1+1)+j-jl1];
        for (int j=jl2; j<=jr2; j++)
            arr[i][j]=a[0][2][(i-il0)*(jr2-jl2+1)+j-jl2];
    }
    for (int i=il1; i<=ir1; i++)
    {
        for (int j=jl0; j<=jr0; j++)
            arr[i][j]=a[1][0][(i-il1)*(jr0-jl0+1)+j-jl0];
        for (int j=jl1; j<=jr1; j++)
            arr[i][j]=a[1][1][(i-il1)*(jr1-jl1+1)+j-jl1];
        for (int j=jl2; j<=jr2; j++)
            arr[i][j]=a[1][2][(i-il1)*(jr2-jl2+1)+j-jl2];
    }
    for (int i=il2; i<=ir2; i++)
    {
        for (int j=jl0; j<=jr0; j++)
            arr[i][j]=a[2][0][(i-il2)*(jr0-jl0+1)+j-jl0];
        for (int j=jl1; j<=jr1; j++)
            arr[i][j]=a[2][1][(i-il2)*(jr1-jl1+1)+j-jl1];
        for (int j=jl2; j<=jr2; j++)
            arr[i][j]=a[2][2][(i-il2)*(jr2-jl2+1)+j-jl2];
    }
    string str;
    for (int i=iltarget; i<=irtarget; i++)
        for (int j=jltarget; j<=jrtarget; j++)
            str.push_back(arr[i][j]);
    for (int i=0; i<100-(irtarget-iltarget+1)*(jrtarget-jltarget+1); i++)
        str.push_back('0');
    if (k!=n-1)
        return str;
    a[0][0]=str;

    int visited[45][45], ans=0;
    for (int i=0; i<=2*n; i++)
        for (int j=0; j<=2*n; j++)
            visited[i][j]=0;
    pair<int, int> adj[4]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    queue<pair<int, int> > q;
    for (int i=0; i<=2*n; i++)
    {
        for (int j=0; j<=2*n; j++)
        {
            if (a[0][0][i*(2*n+1)+j]=='1' && !visited[i][j])
            {
                ans++;
                visited[i][j]=1;
                q.push({i, j});
                while (!q.empty())
                {
                    int ui=q.front().first, uj=q.front().second;
                    q.pop();
                    for (int l=0; l<4; l++)
                    {
                        int vi=ui+adj[l].first, vj=uj+adj[l].second;
                        if (0<=vi && vi<=2*n && 0<=vj && vj<=2*n && a[0][0][vi*(2*n+1)+vj]=='1' && !visited[vi][vj])
                        {
                            visited[vi][vj]=1;
                            q.push({vi, vj});
                        }
                    }
                }
            }
        }
    }
    a[0][0]="";
    for (int i=0; i<10; i++)
        a[0][0].push_back('0'+(bool)(ans&(1<<i)));
    for (int i=0; i<90; i++)
        a[0][0].push_back('0');
    return a[0][0];
}

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