Submission #1247951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247951		chikien2009	Furniture (JOI20_furniture)	C++20	100 / 100	157 ms	4400 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, m, num[2010], q, a, b;
bool blocked[1002][1002], fur[1002][1002];

inline void Up(int x, int y)
{
    if (!blocked[x][y] && blocked[x + 1][y] && blocked[x][y + 1])
    {
        blocked[x][y] = true;
        num[x + y]--;
        Up(x - 1, y);
        Up(x, y - 1);
    }
}

inline void Down(int x, int y)
{
    if (!blocked[x][y] && blocked[x - 1][y] && blocked[x][y - 1])
    {
        blocked[x][y] = true;
        num[x + y]--;
        Down(x + 1, y);
        Down(x, y + 1);
    }
}

int main()
{
    setup();

    cin >> n >> m;
    fill_n(blocked[0], 1002, 1);
    for (int i = 1; i <= n; ++i)
    {
        fill_n(blocked[i], 1002, 1);
        for (int j = 1; j <= m; ++j)
        {
            num[i + j]++;
            cin >> blocked[i][j];
            fur[i][j] = blocked[i][j];
        }
    }
    fill_n(blocked[n + 1], 1002, 1);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (fur[i][j])
            {
                num[i + j]--;
                Up(i - 1, j);
                Up(i, j - 1);
                Down(i + 1, j);
                Down(i, j + 1);
            }
        }
    }
    cin >> q;
    while (q--)
    {
        cin >> a >> b;
        if (!fur[a][b] && (blocked[a][b] || num[a + b] > 1))
        {
            cout << 1 << "\n";
            num[a + b] -= !blocked[a][b];
            fur[a][b] = blocked[a][b] = true;
            Up(a - 1, b);
            Up(a, b - 1);
            Down(a + 1, b);
            Down(a, b + 1);
        }
        else
        {
            cout << 0 << "\n";
        }
    }
    return 0;
}

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