Submission #1225305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225305		KALARRY	Mars (APIO22_mars)	C++20	0 / 100	8 ms	5340 KiB

mars

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,status[100][100][1000];
pair<int,int> info[100][100][1000]; //info[i][j][k] = shows that for (i,j) the kth bit has info for info[i][j][k]
pair<pair<int,int>,int> take_it_from[100][100][1000];
int s_i[100][100];
bool found[100][100];

void calc_info()
{
    for(int i = 0 ; i < N ; i++)
        for(int j = 0 ; j < N ; j++)
        {
            s_i[i][j] = 1;
            info[i][j][0] = {i,j};
        }
    for(int i = N-1 ; i >= 0 ; i--)
        for(int j = N-1 ; j >= 0 ; j--)
        {
            for(int x = 0 ; x < N ; x++)
                for(int y = 0 ; y < N ; y++)
                    found[x][y] = false;
            found[i][j] = true;
            take_it_from[i][j][0] = {{i,j},0};
            int cur_pos = 1;
            for(int x = i+2 ; x >= i ; x--)
                for(int y = j+2 ; y >= j ; y--)
                {
                    if(x==i && y==j)
                        continue;
                        s_i[i][j] += s_i[x][y];
                    for(int l = 0 ; l < s_i[x][y] ; l++)
                    {
                        if(found[info[x][y][l].first][info[x][y][l].second] || (x==(i+1) && y == (j+1)))
                        {
                            s_i[i][j]--;
                            continue;
                        }
                        info[i][j][cur_pos++] = info[x][y][l];
                        take_it_from[i][j][cur_pos - 1] = {{x,y},l};
                        found[info[x][y][l].first][info[x][y][l].second] = true;
                    }
                }
        }

}

int grid[100][100],di[4] = {1,-1,0,0},dj[4] = {0,0,1,-1};
bool visited[100][100];

void dfs(int i,int j)
{
    if(i < 0 || i >= N || j < 0 || j >= N)
        return;
    if(visited[i][j])
        return;
    visited[i][j] = true;
    for(int k = 0 ; k <= 3 ; k++)
    {
        int x = i + di[k];
        int y = j + dj[k];
        dfs(x,y);
    }
}

long long solve()
{
    memset(visited,false,sizeof(visited));
    for(int i = 0 ; i < N ; i++)
        for(int j = 0 ; j < N ; j++)
            if(grid[i][j]==0)
                visited[i][j] = true;
    int ret = 0;
    for(int i = 0 ; i < N ; i++)
        for(int j = 0 ; j < N ; j++)
            if(!visited[i][j])
            {
                ret++;
                dfs(i,j);
            }
    return ret;
}

std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
    N = 2*n + 1;
    calc_info();
    std::string ret(100 ,'0');
    for(int l = 0 ; l < s_i[i][j] ; l++)
    {
        int x = take_it_from[i][j][l].first.first;
        int y = take_it_from[i][j][l].first.second;
        int r = take_it_from[i][j][l].second;
        status[i][j][l] = a[x-i][y-j][r] - '0';

        ret[l] = a[x-i][y-j][r];
    }
    if(k==n-1)
    {
        for(int l = 0 ; l < s_i[i][j] ; l++)
        {
            int x = info[i][j][l].first;
            int y = info[i][j][l].second;
            grid[x][y] = status[i][j][l];
        }
        int ans = solve();
        int pos = 0;
        for(int l = 0 ; l <= 99 ; l++)
        {
            ret[l] = ans%2 + '0';
            ans /= 2;
        }
    }
    return ret;
}

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