oj.uz

Submission #877089

# Submission time Handle Problem Language Result Execution time Memory
877089 2023-11-22T20:37:33 Z parlimoos Furniture (JOI20_furniture) C++14
100 / 100
 170 ms 12912 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define cl clear
#define bg begin
#define lb lower_bound
#define ub upper_bound
#define arr(x) array<int , x>
#define endl '\n'

int n , m , q;
bool mat[1000][1000];
int rcnt[2000];

void del(int i , int j){
    // cout << i << " " << j << "::\n";
    bool shrt = (i >= 0 and j >= 0 and i <= n - 1 and j <= m - 1);
    shrt = (shrt and (!mat[i][j] and (i != 0 or j != 0) and (i != n - 1 or j != m - 1)));
    if(shrt){
        rcnt[i + j]--;
        mat[i][j] = true;
        if(i == 0) del(i , j + 1);
        else if(i == n - 1) del(i , j - 1);
        if(j == 0) del(i + 1 , j);
        else if(j == m - 1) del(i - 1 , j);

        if(i + 1 <= n - 1 and j - 1 >= 0 and mat[i + 1][j - 1]) del(i , j - 1) , del(i + 1 , j);
        if(i - 1 >= 0 and j + 1 <= m - 1 and mat[i - 1][j + 1]) del(i - 1 , j) , del(i , j + 1);
    }
}
void printMat(){
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++) cout << mat[i][j] << " ";
        cout << endl;
    }
    cout << flush;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ; j++) rcnt[i + j]++;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < m ; j++){
            bool d;
            cin >> d;
            if(d) del(i , j);
        }
    }
    // printMat();

    cin >> q;
    for(int i = 0 ; i < q ; i++){
        int x , y;
        cin >> x >> y;
        x-- , y--;
        if(rcnt[x + y] == 1 and !mat[x][y]) cout << "0\n";
        else{
            cout << "1\n";
            del(x , y);
        }
        // printMat();
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 6 ms 860 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 92 ms 5820 KB Output is correct
13 Correct 46 ms 3240 KB Output is correct
14 Correct 149 ms 10844 KB Output is correct
15 Correct 149 ms 11092 KB Output is correct
16 Correct 164 ms 11828 KB Output is correct
17 Correct 162 ms 12592 KB Output is correct
18 Correct 164 ms 12116 KB Output is correct
19 Correct 169 ms 12872 KB Output is correct
20 Correct 170 ms 12880 KB Output is correct
21 Correct 169 ms 12912 KB Output is correct