oj.uz

Submission #349027

# Submission time Handle Problem Language Result Execution time Memory
349027 2021-01-16T10:58:47 Z apostoldaniel854 Furniture (JOI20_furniture) C++14
100 / 100
 303 ms 13036 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int MAX_N = 1000;
bool blocked[1 + MAX_N + 1][1 + MAX_N + 1];
int diag[1 + 2 * MAX_N];

int n, m;
void go_stupid (int x, int y) {
    if (x >= 1 && x <= n && y >= 1 && y <= m) {
        if (not blocked[x][y]) {
            blocked[x][y] = true;
            diag[x + y]--;
            if (x == 1 ||  y == m || blocked[x - 1][y + 1]) {
                go_stupid (x, y + 1);
                go_stupid (x - 1, y);
            }
            if (x == n || y == 1 || blocked[x + 1][y - 1]) {
                go_stupid (x, y - 1);
                go_stupid (x + 1, y);
            }
        }
    }
}
int main() {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            diag[i + j]++;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            if (x)
                go_stupid (i, j);
        }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (blocked[x][y])
            cout << "1\n";
        else if (diag[x + y] == 1)
            cout << "0\n";
        else {
            cout << "1\n";
            go_stupid (x, y);
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 4 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 9 ms 748 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 139 ms 5996 KB Output is correct
13 Correct 64 ms 3180 KB Output is correct
14 Correct 245 ms 10988 KB Output is correct
15 Correct 296 ms 11116 KB Output is correct
16 Correct 255 ms 12268 KB Output is correct
17 Correct 277 ms 12896 KB Output is correct
18 Correct 262 ms 12268 KB Output is correct
19 Correct 303 ms 13036 KB Output is correct
20 Correct 268 ms 13036 KB Output is correct
21 Correct 284 ms 13036 KB Output is correct