Submission #1180731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180731		MarwenElarbi	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	576 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
int n,m;
int grid[1005][1005];
vector<int> tab(2005);
void display(){
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cout <<grid[i][j]<<" ";
        }cout <<endl;
    }cout <<endl;
    for (int i = 0; i < n+m; ++i)
    {
        cout <<tab[i]<<" ";
    }cout <<endl;
}
bool valid(int x,int y){
    return (x>=0 & y>= 0 & x < n & y < m) ;
}
void dfs(int x,int y,int cur){
    if(!valid(x,y)) return;
    if(grid[x][y]==1) return;
    if(cur==-1){
        tab[x+y]--;
        grid[x][y]=1;
        dfs(x+1,y,0);
        dfs(x-1,y,2);
        dfs(x,y+1,1);
        dfs(x,y-1,3);
    }else if(cur==0){
        if(y== 0 || grid[x][y-1] == 1){
            tab[x+y]--;
            grid[x][y]=1;
            dfs(x+1,y,0);
            dfs(x,y+1,1);
            dfs(x,y-1,3);
        }
    }else if(cur==1){
        if(x== 0 || grid[x-1][y] == 1){
            tab[x+y]--;
            grid[x][y]=1;
            dfs(x+1,y,0);
            dfs(x,y+1,1);
            dfs(x-1,y,2);
        }
    }else if(cur==2){
        if(y== m-1 || grid[x][y+1] == 1){
            tab[x+y]--;
            grid[x][y]=1;
            dfs(x,y+1,1);
            dfs(x-1,y,2);
            dfs(x,y-1,3);
        }
    }else{
        if(x== n-1 || grid[x+1][y] == 1){
            tab[x+y]--;
            grid[x][y]=1;
            dfs(x-1,y,2);
            dfs(x,y-1,3);
            dfs(x+1,y,0);
        }
    }
}
int main() {
    cin>>n>>m;
    vector<pair<int,int>> q;
    for (int i = 0; i < m; ++i)
    {
        tab[i]=min(i+1,n);
    }
    for (int i = m; i < m+n-1; ++i)
    {
        tab[i]=min(m+n-i-1,m);
    }
    int cnt=0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin>>grid[i][j];
            if(grid[i][j]==1){
                q.push_back({i,j});
                cnt++;
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            grid[i][j]=0;
        }
    }
    int k;
    cin>>k;
    for (int i = 0; i < k; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        q.push_back({x,y});
    }
    for (int i = 0; i < q.size(); ++i)
    {
        int x=q[i].first;
        int y=q[i].second;
        if(grid[x][y]==1) cout <<1<<endl;
        else if(tab[x+y]==1){
            if(i>=cnt) cout << 0 << endl;
        }else{
            if(i>=cnt) cout << 1 <<endl;
            dfs(x,y,-1);
        }
        //display();
    }
}

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