Submission #1049180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049180		not_amir	Furniture (JOI20_furniture)	C++14	0 / 100	1 ms	600 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

vector<vector<bool>> top, bottom, pos;

int n, m;

void rem_top(int x, int y){
    int i, j;
    for(i = x; i >= 0 && top[i][y]; i--){
        top[i][y] = 0;
        top[i][y - 1] = 1;
    }
    for(j = y + 1; j < m && top[x][j]; j++){
        top[x][j] = 0;
        top[x + 1][j] = 1;
    }
    top[x + 1][y - 1] = 1;
    for(i++; i < x + 1; i++){
        if(pos[i][y - 1]){
            rem_top(i, y - 1);
            return;
        }
    }
    for(y--; y < j; y++){
        if(pos[x + 1][y]){
            rem_top(x + 1, y);
            return;
        }
    }
}

void rem_bottom(int x, int y){
    int i, j;
    for(i = x; i < n && bottom[i][y]; i++){
        bottom[i][y] = 0;
        bottom[i][y + 1] = 1;
    }
    for(j = y - 1; j >= 0 && bottom[x][j]; j--){
        bottom[x][j] = 0;
        bottom[x - 1][j] = 1;
    }
    bottom[x - 1][y + 1] = 1;
    for(j++; j < y + 1; j++){
        if(pos[x + 1][j]){
            rem_top(x + 1, j);
            return;
        }
    }
    for(x--; x < i; x++){
        if(pos[x][y + 1]){
            rem_top(x, y + 1);
            return;
        }
    }
}

int main(){
    cin >> n >> m;
    top.resize(n, vector<bool>(m));
    bottom.resize(n, vector<bool>(m));
    pos.resize(m, vector<bool>(m));
    for(int i = 0; i < n; i++){
        top[i][m - 1] = 1;
        bottom[i][0] = 1;
    }
    for(int j = 0; j < m; j++){
        top[0][j] = 1;
        bottom[n - 1][j] = 1;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int C;
            cin >> C;
            if(!C)
                continue;
            pos[i][j] = 1;
            if(top[i][j])
                rem_top(i, j);
            if(bottom[i][j])
                rem_bottom(i, j);
        }
    }
    int q;
    cin >> q;
    while(q--){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        if(top[x][y] && bottom[x][y]){
            cout << "0 ";
        }
        else{
            pos[x][y] = 1;
            if(top[x][y])
                rem_top(x, y);
            if(bottom[x][y])
                rem_bottom(x, y);
            cout << "1 ";
        }
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95