oj.uz

Submission #683319

# Submission time Handle Problem Language Result Execution time Memory
683319 2023-01-18T07:44:10 Z MarcuMihai Furniture (JOI20_furniture) C++14
0 / 100
 5000 ms 852 KB 
#include <bits/stdc++.h>

using namespace std;

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+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-1][j]==1 && dp[i][j-1]==1)
    {
        dp[i][j]=1;
        schimbjos(i+1,j);
        schimbjos(i,j+1);
    }
}

int main()
{
    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)
            cout<<dp[i][j]<<" ";
        cout<<"\n";
    }




    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 852 KB Time limit exceeded
2 Halted 0 ms 0 KB -