Submission #1146255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146255		ace5	Furniture (JOI20_furniture)	C++20	100 / 100	213 ms	10304 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> a;
vector<vector<int>> r;
vector<int> rs;
vector<pair<int,int>> d = {{1,0},{0,1},{0,-1},{-1,0}};

int sfr(int i,int j)
{
    return ((i < 0 || i >= a.size() || j < 0 || j >= a[0].size()) ? 0 : r[i][j]);
}

void dfs(int i,int j)
{
    //cout << i << ' ' << j << endl;
    if(i < 0 || i >= a.size() || j < 0 || j >= a[0].size() || r[i][j] == 0)
        return;
    int y = 0;
    if(sfr(i-1,j) == 0  && sfr(i,j-1) == 0 && i+j > 0)
    {
        y =1;
    }
    if(sfr(i+1,j) == 0  && sfr(i,j+1) == 0 && i+j+2 < a.size() + a[0].size())
    {
        y =1;
    }
    if(!y)
        return ;
    //cout << i << ' ' << j << endl;
    r[i][j] = 0;
    rs[i+j] --;
    for(int k = 0;k < 4;++k)
        dfs(i+d[k].first,j+d[k].second);
}

bool block(int i,int j)
{
    if(rs[i+j] == 1 && r[i][j] == 1)
    {
        return false;
    }
    else
    {
        if(r[i][j] == 0)
        {
            a[i][j] = 1;
            return true;
        }
        a[i][j] = 1;
        r[i][j] = 0;
        rs[i+j]--;
        for(int k = 0;k < 4;++k)
            dfs(i+d[k].first,j+d[k].second);
        return true;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin >> n >> m;
    a.resize(n);
    r.resize(n);
    rs.resize(n+m-1);
    for(int j = 0;j < n;++j)
    {
        a[j].resize(m);
        r[j].resize(m);
        for(int u = 0;u < m;++u)
        {
            a[j][u] = 0;
            r[j][u] = 1;
            rs[j+u]++;
        }
    }
    for(int i = 0;i < n;++i)
    {
        for(int j = 0;j < m;++j)
        {
            int x;
            cin >> x;
            if(x == 1)
            {
                block(i,j);
            }
        }
    }
    int q;
    cin >> q;
    while(q--)
    {
        int i,j;
        cin >> i >> j;
        i--;
        j--;
        cout << (block(i,j) ? 1 : 0) << "\n";
    }
}

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