oj.uz

Submission #303385

# Submission time Handle Problem Language Result Execution time Memory
303385 2020-09-20T09:24:57 Z polipolinom Furniture (JOI20_furniture) C++14
100 / 100
 3423 ms 20404 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1042;
int c[MAX_N][MAX_N];
int ans[MAX_N][MAX_N];
int sum[MAX_N * 2];

void add (queue < pair < int, int > >& q, int x, int y) {
    if (ans[x][y] == 1) {
        //cout << x << " " << y << endl;
        ans[x][y] = 0;
        sum[x + y]--;
        q.push({x, y});
    }
}

int change(int x, int y) {
    if (ans[x][y] == 0) {
        return 1;
    }
    if (sum[x + y] == 1) {
        return 0;
    }
    queue < pair < int, int > > q;
    add(q, x, y);
    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        if (ans[x - 1][y + 1] == 0) {
            add(q, x - 1, y);
            add(q, x, y + 1);
        }
        if (ans[x + 1][y - 1] == 0) {
            add(q, x + 1, y);
            add(q, x, y - 1);
        }
    }
    return 1;
}

int main() {
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            sum[i + j]++;
            ans[i][j] = 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            if (c[i][j]) {
                change(i, j);
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int i, j;
        cin >> i >> j;
        cout << change(i, j) << "\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 14 ms 1152 KB Output is correct
4 Correct 27 ms 1152 KB Output is correct
5 Correct 28 ms 1280 KB Output is correct
6 Correct 33 ms 1280 KB Output is correct
7 Correct 33 ms 1408 KB Output is correct
8 Correct 32 ms 1280 KB Output is correct
9 Correct 32 ms 1280 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 14 ms 1152 KB Output is correct
4 Correct 27 ms 1152 KB Output is correct
5 Correct 28 ms 1280 KB Output is correct
6 Correct 33 ms 1280 KB Output is correct
7 Correct 33 ms 1408 KB Output is correct
8 Correct 32 ms 1280 KB Output is correct
9 Correct 32 ms 1280 KB Output is correct
10 Correct 86 ms 1160 KB Output is correct
11 Correct 21 ms 768 KB Output is correct
12 Correct 1237 ms 13304 KB Output is correct
13 Correct 296 ms 9976 KB Output is correct
14 Correct 2834 ms 17560 KB Output is correct
15 Correct 2949 ms 17936 KB Output is correct
16 Correct 3184 ms 18924 KB Output is correct
17 Correct 3326 ms 19828 KB Output is correct
18 Correct 3284 ms 19340 KB Output is correct
19 Correct 3423 ms 20332 KB Output is correct
20 Correct 3374 ms 20404 KB Output is correct
21 Correct 3396 ms 20016 KB Output is correct