Submission #423733

#	Time	Username	Problem	Language	Result	Execution time	Memory
423733		tengiz05	Furniture (JOI20_furniture)	C++17	100 / 100	401 ms	3596 KiB

furniture

#include <bits/stdc++.h>
constexpr int N = 1005;
char c[N][N];
int n, m, sum[2 * N], all[2 * N];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m;
    memset(c, '1', sizeof c);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            std::cin >> c[i][j];
            sum[i + j] += c[i][j] == '1';
            all[i + j]++;
        }
    }
    auto check = [&](int i, int j) {
        if (i <= 0 || j <= 0 || i > n && j > m || i + j == 2) return false;
        return (c[i][j] == '0' || c[i - 1][j - 1] == '0') && c[i - 1][j] == '1' && c[i][j - 1] == '1';
    };
    std::function<void(int, int)> work = [&](int x, int y) {
        sum[x + y] += c[x][y] == '0';
        c[x][y] = '1';
        sum[x - 1 + y - 1] += c[x - 1][y - 1] == '0';
        c[x - 1][y - 1] = '1';
        for (int i = -2; i < 3; i++) {
            for (int j = -2; j < 3; j++) {
                if (check(x + i, y + j)) {
                    work(x + i, y + j);
                }
            } 
        }
    };
    for (int i = 1; i <= n + 1; i++) {
        for (int j = 1; j <= m + 1; j++) {
            if (i + j == 2 || i + j == n + m + 2) continue;
            if (c[i - 1][j] == '1' && c[i][j - 1] == '1') {
                work(i, j);
            }
        }
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        int x, y;
        std::cin >> x >> y;
        if (c[x][y] == '1') {
            std::cout << 1 << "\n";
        } else {
            if (all[x + y] - sum[x + y] > 1) {
                std::cout << 1 << "\n";
                c[x][y] = '1';
                sum[x + y]++;
                for (int i = -2; i < 3; i++) {
                    for (int j = -2; j < 3; j++) {
                        if (check(x + i, y + j)) {
                            work(x + i, y + j);
                        }
                    } 
                }
            } else {
                std::cout << 0 << "\n";
            }
        }
    }
    return 0;
}

Compilation message (stderr)

furniture.cpp: In lambda function:
furniture.cpp:18:39: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |         if (i <= 0 || j <= 0 || i > n && j > m || i + j == 2) return false;
      |                                 ~~~~~~^~~~~~~~

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