oj.uz

Submission #595079

# Submission time Handle Problem Language Result Execution time Memory
595079 2022-07-13T10:49:57 Z elkernos Furniture (JOI20_furniture) C++17
100 / 100
 253 ms 12188 KB 
#include <bits/stdc++.h>

using namespace std;

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> good(n + 2, vector<bool>(m + 2));
    vector<int> cnt(n + m + 1);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            good[i][j] = 1;
            cnt[i + j]++;
        }
    }
    auto put = [&](int X, int Y) {
        if(!good[X][Y]) {
            return 1;
        }
        if(cnt[X + Y] == 1) {
            return 0;
        }
        function<void(int, int)> dfs = [&](int x, int y) {
            auto maybe = [&](int tx, int ty) {
                if(good[tx][ty]) {
                    good[tx][ty] = 0;
                    cnt[tx + ty]--;
                    dfs(tx, ty);
                }
            };
            if(!good[x - 1][y + 1]) {
                maybe(x - 1, y);
                maybe(x, y + 1);
            }
            if(!good[x + 1][y - 1]) {
                maybe(x, y - 1);
                maybe(x + 1, y);
            }
        };
        good[X][Y] = 0;
        cnt[X + Y]--;
        dfs(X, Y);
        return 1;
    };
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int c;
            cin >> c;
            if(c == 1) {
                put(i, j);
            }
        }
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << put(x, y) << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 324 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 416 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 324 KB Output is correct
5 Correct 3 ms 328 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 416 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 9 ms 724 KB Output is correct
11 Correct 3 ms 404 KB Output is correct
12 Correct 173 ms 5248 KB Output is correct
13 Correct 55 ms 2388 KB Output is correct
14 Correct 224 ms 10000 KB Output is correct
15 Correct 237 ms 10352 KB Output is correct
16 Correct 229 ms 11224 KB Output is correct
17 Correct 240 ms 11740 KB Output is correct
18 Correct 244 ms 11472 KB Output is correct
19 Correct 253 ms 12108 KB Output is correct
20 Correct 252 ms 12184 KB Output is correct
21 Correct 251 ms 12188 KB Output is correct