oj.uz

Submission #683558

# Submission time Handle Problem Language Result Execution time Memory
683558 2023-01-18T17:49:46 Z MarcuMihai Furniture (JOI20_furniture) C++14
100 / 100
 313 ms 19816 KB 
#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;
                --diag[i+j].ocup;

        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=0; i<=n+1; ++i)
        dp[i][0]=dp[i][m+1]=1;
    for(int i=0; i<=m+1; ++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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 3 ms 1216 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 4 ms 1248 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 3 ms 1216 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 4 ms 1248 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 8 ms 1108 KB Output is correct
11 Correct 4 ms 816 KB Output is correct
12 Correct 135 ms 12740 KB Output is correct
13 Correct 54 ms 9648 KB Output is correct
14 Correct 238 ms 17128 KB Output is correct
15 Correct 238 ms 17356 KB Output is correct
16 Correct 223 ms 18488 KB Output is correct
17 Correct 313 ms 19404 KB Output is correct
18 Correct 244 ms 18828 KB Output is correct
19 Correct 254 ms 19816 KB Output is correct
20 Correct 254 ms 19788 KB Output is correct
21 Correct 258 ms 19812 KB Output is correct