제출 #1260695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260695		tvgk	Furniture (JOI20_furniture)	C++20	100 / 100	181 ms	11388 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 1e3 + 7;

int cnt[mxN * 2], in[mxN][mxN][2], nRow, nCol;
bool path[mxN][mxN];

void Upd(int u, int v, bool tt)
{
    cnt[u + v] -= path[u][v];
    path[u][v] = 0;
    in[u][v][tt] = 0;

    if (!tt)
    {
        if (--in[u + 1][v][tt] == 0)
            Upd(u + 1, v, tt);
        if (--in[u][v + 1][tt] == 0)
            Upd(u, v + 1, tt);
    }
    else
    {
        if (--in[u - 1][v][tt] == 0)
            Upd(u - 1, v, tt);
        if (--in[u][v - 1][tt] == 0)
            Upd(u, v - 1, tt);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);

    cin >> nRow >> nCol;
    for (int i = 1; i <= nRow; i++)
    {
        for (int j = 1; j <= nCol; j++)
        {
            cnt[i + j]++;
            in[i][j][0] = (i > 1) + (j > 1);
            in[i][j][1] = (i < nRow) + (j < nCol);
            path[i][j] = 1;
        }
    }
    in[1][1][0] = in[nRow][nCol][1] = 1;

    for (int i = 1; i <= nRow; i++)
    {
        for (int j = 1; j <= nCol; j++)
        {
            bool tt;
            cin >> tt;
            if (tt && in[i][j][0] > 0)
                Upd(i, j, 0);
            if (tt && in[i][j][1] > 0)
                Upd(i, j, 1);
        }
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;

        if (cnt[u + v] == 1 && path[u][v])
        {
            cout << 0 << '\n';
            continue;
        }
        cout << 1 << '\n';

        if (in[u][v][0] > 0)
            Upd(u, v, 0);
        if (in[u][v][1] > 0)
            Upd(u, v, 1);
    }
}

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