oj.uz

Submission #492090

# Submission time Handle Problem Language Result Execution time Memory
492090 2021-12-05T11:42:13 Z alextodoran Furniture (JOI20_furniture) C++17
100 / 100
 277 ms 4164 KB 
/**
 ____ ____ ____ ____ ____
||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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 3 ms 468 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 4 ms 460 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 10 ms 588 KB Output is correct
11 Correct 2 ms 424 KB Output is correct
12 Correct 147 ms 2460 KB Output is correct
13 Correct 71 ms 1972 KB Output is correct
14 Correct 231 ms 3476 KB Output is correct
15 Correct 264 ms 3584 KB Output is correct
16 Correct 242 ms 3740 KB Output is correct
17 Correct 262 ms 3944 KB Output is correct
18 Correct 263 ms 3760 KB Output is correct
19 Correct 262 ms 4164 KB Output is correct
20 Correct 248 ms 3928 KB Output is correct
21 Correct 277 ms 3920 KB Output is correct