Submission #492090

#	Time	Username	Problem	Language	Result	Execution time	Memory
492090		alextodoran	Furniture (JOI20_furniture)	C++17	100 / 100	277 ms	4164 KiB

furniture

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int NM_MAX = 1000;

int N, M;

bool inPath[NM_MAX + 2][NM_MAX + 2];

int sumCount[NM_MAX * 2 + 2];

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

bool inside (int x, int y) {
    return (1 <= x && x <= N && 1 <= y && y <= M);
}

bool check (int x, int y) {
    if (x == 1 && y == 1 || x == N && y == M) {
        return true;
    }else if (inPath[x + 1][y] == false && inPath[x][y + 1] == false) {
        return false;
    } else if (inPath[x - 1][y] == false && inPath[x][y - 1] == false) {
        return false;
    } else {
        return true;
    }
}

bool placeBlock (int X, int Y) {
    if (inPath[X][Y] == false) {
        return true;
    }
    if (sumCount[X + Y] == 1) {
        return false;
    }

    queue <pair <int, int>> q;

    inPath[X][Y] = false;
    sumCount[X + Y]--;
    q.push(make_pair(X, Y));

    while (q.empty() == false) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int d = 0; d < 4; d++) {
            int x1 = x + dx[d], y1 = y + dy[d];
            if (inside(x1, y1) == true && inPath[x1][y1] == true && check(x1, y1) == false) {
                inPath[x1][y1] = false;
                sumCount[x1 + y1]--;
                q.push(make_pair(x1, y1));
            }
        }
    }

    return true;
}

int Q;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= M; y++) {
            inPath[x][y] = true;
            sumCount[x + y]++;
        }
    }

    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= M; y++) {
            bool init;
            cin >> init;
            if (init == true) {
                assert(placeBlock(x, y) == true);
            }
        }
    }

    cin >> Q;
    while (Q--) {
        int X, Y;
        cin >> X >> Y;
        cout << placeBlock(X, Y) << "\n";
    }

    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'bool check(int, int)':
furniture.cpp:30:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   30 |     if (x == 1 && y == 1 || x == N && y == M) {
      |         ~~~~~~~^~~~~~~~~

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