Submission #683331

#	Time	Username	Problem	Language	Result	Execution time	Memory
683331		MarcuMihai	Furniture (JOI20_furniture)	C++14	0 / 100	2 ms	1108 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

ifstream f ("date.in");
ofstream g ("date.out");


int n,m;
int a[1005][1005];
int dp[1005][1005];
struct el
{
    int st;
    int dr;
    int ocup;
};
el diag[2005];

void schimbsus(int i, int j)
{
    if(i==0 || i==n+1 || j==0 || j==m+1)
        return;

    if(dp[i][j]==0 && dp[i+1][j]==1 && dp[i][j+1]==1)
    {
        dp[i][j]=1;
        --diag[i+j].ocup;
        schimbsus(i-1,j);
        schimbsus(i,j-1);
    }
}

void schimbdiag(int dig, int &st, int &dr, int lin)
{
    if(st==lin || dp[st][dig-st]==1)
    {
        for(int i=st+1; i<=dr; ++i)
            if(dp[i][dig-i]==0)
            {
                st=i;
                break;
            }
    }
    if(dr==lin || dp[dr][dig-dr]==1)
    {
        for(int i=dr-1; i>=st; --i)
            if(dp[i][dig-i]==0)
            {
                dr=i;
                break;
            }
    }
}

void schimbjos(int i, int j)
{
    if(i==0 || i==n+1 || j==0 || j==m+1)
        return;

    if(dp[i][j]==0 && dp[i-1][j]==1 && dp[i][j-1]==1)
    {
        dp[i][j]=1;
        schimbjos(i+1,j);
        schimbjos(i,j+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            cin>>a[i][j];
            if(a[i][j]==1)
                dp[i][j]=1;
        }
    for(int i=1; i<=n; ++i)
        dp[i][0]=dp[i][m+1]=1;
    for(int i=1; i<=m; ++i)
        dp[0][i]=dp[n+1][i]=1;

    for(int i=n; i>0; --i)
    {
        for(int j=m; j>0; --j)
        {
            if(a[i][j]==0 && (dp[i+1][j]==0 || dp[i][j+1]==0))
                dp[i][j]=0;
            else if((i!=1 || j!=1) && (i!=n || j!=m))
                dp[i][j]=1;
        }
    }

    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            if(a[i][j]==0 && (dp[i-1][j]==0 || dp[i][j-1]==0))
                continue;

            else if((i!=1 || j!=1) && (i!=n || j!=m))
                dp[i][j]=1;
        }
    }


    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
            if(dp[i][j]==0)
            {
                diag[i+j].dr=max(diag[i+j].dr, i);
                if(diag[i+j].st==0)
                    diag[i+j].st=i;
                diag[i+j].ocup++;
            }

    int q;
    cin>>q;
    for(int query=1; query<=q; ++query)
    {
        int i, j;
        cin>>i>>j;
        if(dp[i][j]==1)
            cout<<1<<"\n";
        else
        {
            if(diag[i+j].ocup==1)
                cout<<0<<"\n";
            else
            {
                schimbdiag(i+j, diag[i+j].st, diag[i+j].dr, i);
                dp[i][j]=1;
                --diag[i+j].ocup;
                cout<<1<<"\n";
                schimbsus(i-1,j);
                schimbsus(i,j-1);
                schimbjos(i+1,j);
                schimbjos(i,j+1);
            }
        }
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95