Submission #877089

#	Time	Username	Problem	Language	Result	Execution time	Memory
877089		parlimoos	Furniture (JOI20_furniture)	C++14	100 / 100	170 ms	12912 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95