oj.uz

Submission #423733

# Submission time Handle Problem Language Result Execution time Memory
423733 2021-06-11T12:03:45 Z tengiz05 Furniture (JOI20_furniture) C++17
100 / 100
 401 ms 3596 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct
5 Correct 5 ms 1356 KB Output is correct
6 Correct 5 ms 1352 KB Output is correct
7 Correct 5 ms 1356 KB Output is correct
8 Correct 7 ms 1356 KB Output is correct
9 Correct 6 ms 1356 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct
5 Correct 5 ms 1356 KB Output is correct
6 Correct 5 ms 1352 KB Output is correct
7 Correct 5 ms 1356 KB Output is correct
8 Correct 7 ms 1356 KB Output is correct
9 Correct 6 ms 1356 KB Output is correct
10 Correct 18 ms 1600 KB Output is correct
11 Correct 4 ms 1356 KB Output is correct
12 Correct 230 ms 2212 KB Output is correct
13 Correct 68 ms 1740 KB Output is correct
14 Correct 350 ms 3200 KB Output is correct
15 Correct 358 ms 3260 KB Output is correct
16 Correct 388 ms 3268 KB Output is correct
17 Correct 360 ms 3356 KB Output is correct
18 Correct 384 ms 3252 KB Output is correct
19 Correct 401 ms 3536 KB Output is correct
20 Correct 386 ms 3596 KB Output is correct
21 Correct 361 ms 3568 KB Output is correct