oj.uz

Submission #707042

# Submission time Handle Problem Language Result Execution time Memory
707042 2023-03-08T10:37:51 Z someone Furniture (JOI20_furniture) C++14
100 / 100
 378 ms 30380 KB 
#include <bits/stdc++.h>
#define int long long
#define a second
#define b first
using namespace std;

const int N = 1e3 + 42, INF = 1e18 + 42;

bool pos[N][N][2];
int n, m, q, nb[2*N], pre[N][N][2];

int delta[] = {1, -1};

void flood(int i, int j, int id) {
    if(i >= n || j >= m || i < 0 || j < 0 || !pos[i][j][id])
        return;
    pre[i][j][id]--;
    if(pre[i][j][id] == 0) {
        if(pos[i][j][0] && pos[i][j][1])
            nb[i + j]--;
        pos[i][j][id] = false;
        flood(i + delta[id], j, id);
        flood(i, j + delta[id], id);
    }
}

bool furniture(int i, int j) {
    if(pos[i][j][0] && pos[i][j][1] && nb[i + j] == 1)
        return false;
    pre[i][j][0] = 1;
    pre[i][j][1] = 1;
    flood(i, j, 0);
    flood(i, j, 1);
    return true;
}

signed main() {
    ios::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++) {
            nb[i + j]++;
            if(i != 0) pre[i][j][0]++;
            if(j != 0) pre[i][j][0]++;
            if(i != n-1) pre[i][j][1]++;
            if(j != m-1) pre[i][j][1]++;
            pos[i][j][0] = pos[i][j][1] = true;
        }
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++) {
            int x; cin >> x;
            if(x) furniture(i, j);
        }
    
    cin >> q;
    for(int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        cout << furniture(x-1, y-1) << '\n';
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct
7 Correct 4 ms 1248 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 1108 KB Output is correct
10 Correct 10 ms 1748 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 178 ms 23236 KB Output is correct
13 Correct 59 ms 19660 KB Output is correct
14 Correct 336 ms 27072 KB Output is correct
15 Correct 350 ms 27220 KB Output is correct
16 Correct 378 ms 28576 KB Output is correct
17 Correct 365 ms 29788 KB Output is correct
18 Correct 337 ms 28920 KB Output is correct
19 Correct 348 ms 30380 KB Output is correct
20 Correct 294 ms 30300 KB Output is correct
21 Correct 304 ms 30340 KB Output is correct