oj.uz

Submission #715655

# Submission time Handle Problem Language Result Execution time Memory
715655 2023-03-27T12:14:25 Z Farbod Furniture (JOI20_furniture) C++17
100 / 100
 264 ms 11304 KB 
/*
*  In the name of God
*
*  Author: Farbod Doost
*  Last Modified: Mon, 27 Mar 2023 (15:40:12)
*
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, m, par[N][N], c[N][N], cnt[N << 1];
bool vis[N][N];

void del(int i, int j)
{
    if (vis[i][j])
        return;
    vis[i][j] = 1;

    cnt[i + j]--;
    if (i < n - 1) {
        par[i + 1][j]--;
        if (par[i + 1][j] == 0)
            del(i + 1, j);
    }
    if (j < m - 1) {
        par[i][j + 1]--;
        if (par[i][j + 1] == 0)
            del(i, j + 1);
    }
    if (i > 0) {
        c[i - 1][j]--;
        if (c[i - 1][j] == 0)
            del(i - 1, j);
    }
    if (j > 0) {
        c[i][j - 1]--;
        if (c[i][j - 1] == 0)
            del(i, j - 1);
    }

    return;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            par[i][j] = c[i][j] = 2;
            if (i == 0)
                par[i][j]--;
            if (j == 0)
                par[i][j]--;
            if (i == n - 1)
                c[i][j]--;
            if (j == m - 1)
                c[i][j]--;

            cnt[i + j]++;
        }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            bool x;
            cin >> x;

            if (x)
                del(i, j);
        }

    int q;
    cin >> q;

    while (q--) {
        int i, j;
        cin >> i >> j, i--, j--;

        if (!vis[i][j] && cnt[i + j] == 1)
            cout << "0\n";
        else
            del(i, j), cout << "1\n";
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 4 ms 1236 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 3 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 4 ms 1236 KB Output is correct
9 Correct 3 ms 1236 KB Output is correct
10 Correct 9 ms 980 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 131 ms 9756 KB Output is correct
13 Correct 62 ms 8868 KB Output is correct
14 Correct 209 ms 10204 KB Output is correct
15 Correct 215 ms 10376 KB Output is correct
16 Correct 228 ms 10588 KB Output is correct
17 Correct 237 ms 11200 KB Output is correct
18 Correct 250 ms 10728 KB Output is correct
19 Correct 264 ms 11304 KB Output is correct
20 Correct 228 ms 11144 KB Output is correct
21 Correct 247 ms 11236 KB Output is correct