Submission #1225366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225366		KALARRY	Mars (APIO22_mars)	C++20	14 / 100	49 ms	17832 KiB

mars

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,status[100][100][1000],col[100][100];
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()
{
    if(N <= 10)
    {
        for(int i = 0 ; i < N ; i+=2)
            for(int j = 0 ; j < N ; j++)
                if(j%2==1)
                    col[i][j] = 1;
                else
                    col[i][j] = 2;
        for(int i = 1 ; i < N ; i+=2)
            for(int j = 0 ; j < N ; j++)
                if(j%2==1)
                    col[i][j] = 3;
                else
                    col[i][j] = 4;
    }
    else
    {
        for(int j = 0 ; j < N ; j++)
            if(j%2==1)
                col[0][j] = 1;
            else
                col[0][j] = 2;    
        for(int j = 0 ; j < N ; j++)
            if(j%2==1)
                col[1][j] = 3;
            else
                col[1][j] = 4;
        int turn = 5;
        for(int i = 2 ; i < N ; i++)
        {
            int other = 1;
            for(int j = 0 ; j < N ; j++)
                if(j%2==1)
                {
                    col[i][j] = other;
                    other++;
                    if(other==turn)
                        other++;
                    if(other==6)
                        other = 1;
                    if(other==turn)
                        other++;
                }
                else
                    col[i][j] = turn;
            turn++;
            if(turn==6)
                turn = 1;
        }
    }
    

    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] || (col[i][j] != col[x][y]))
                        {
                            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;
                    }
                }
            if(s_i[i][j] > 100)
                sleep(10000000);                
        }
}

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 r = 0 ; r <= 2 ; r++)
            for(int s = 0 ; s <= 2 ; s++)
            {
                if(r==0 && s==0)
                    continue;
                for(int l = 0 ; l < s_i[i][j] ; l++)
                    status[r][s][l] = a[r-i][s-i][l] - '0';
            }
        while(i <= 2)
        {
            j = 0;
            while(j <= 2)
            {
                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];
                }
                j++;
            }
            i++;
        }
        int ans = solve();
        int pos = 0;
        for(int l = 0 ; l <= 99 ; l++)
        {
            ret[l] = ans%2 + '0';
            ans /= 2;
        }
    }
    return ret;
}

• 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