Submission #470968

#	Time	Username	Problem	Language	Result	Execution time	Memory
470968		iulia13	Furniture (JOI20_furniture)	C++14	0 / 100	296 ms	524292 KiB

furniture

#include <bits/stdc++.h>

using namespace std;
const int N = 1005;
int n, m;
int a[N][N];
int SePoate[N][N];
int diag[N + N];
int b = 1;
struct ura{
    int x, y;
};
int dL[4] = {0, 1, 0, -1};
int dC[4] = {1, 0, -1, 0};
int verif(int x, int y)
{
    if (x < 1 || y < 1 || n < x || m < y)
        return 1;
    return 0;
}
void lee(int xs, int ys, int l, int r)
{
    queue <ura> q;
    SePoate[xs][ys] += b;
    q.push({xs, ys});
    while (!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        for (int i = l; i <= r; i++)
        {
            int xx = x + dL[i];
            int yy = y + dC[i];
            if (verif(xx, yy) || a[xx][yy])
                continue;
            if (SePoate[xx][yy] < b)
            {
                SePoate[xx][yy] += b;
                q.push({xx, yy});
            }
        }
    }

}
void upd(int x, int y)
{

    diag[x + y]--;
    SePoate[x][y] = 0;
    for (int i = -1; i <= 1; i += 2)
        for (int j = -1; j <= 1; j += 2)
        {
            int xx = x + i;
            int yy = y + j;
            if (verif(xx, yy) || SePoate[xx][yy])
                continue;
            int mx = max(xx, x);
            int my = max(yy, y);
            if (SePoate[mx][my])
                upd(x, y);
        }
}
int main()
{
    int i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> a[i][j];
    lee(1, 1, 0, 1);
    b++;
    lee(n, m, 2, 3);
    for(i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            if (SePoate[i][j] == 3)
                SePoate[i][j] = 1;
            else
                SePoate[i][j] = 0;
            diag[i + j] += SePoate[i][j];
        }
    int q;
    cin >> q;
    while(q--)
    {
        int x, y;
        cin >> x >> y;
        if (SePoate[x][y] == 0)
        {
            cout << 1 << '\n';
            continue;
        }
        if (diag[x + y] > 1)
        {
            cout << 1 << '\n';
            upd(x, y);
            continue;
        }
        cout << 0 << '\n';
    }
    return 0;
}

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