Submission #362154

#	Time	Username	Problem	Language	Result	Execution time	Memory
362154		doowey	Furniture (JOI20_furniture)	C++14	0 / 100	3 ms	364 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 1010;
int C[N][N];
bool is_up[N][N];
bool is_down[N][N];

int main(){
    fastIO;
    freopen("in.txt","r",stdin);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            cin >> C[i][j];
        }
    }
    is_up[1][1]=true;
    is_down[n][m]=true;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            if(i == 1 && j == 1) continue;
            if(C[i][j]==1) continue;
            is_up[i][j] = (is_up[i][j-1]|is_up[i-1][j]);
        }
    }
    for(int i = n; i >= 1; i -- ){
        for(int j = m ; j >= 1; j -- ){
            if(i==n && j == m) continue;
            if(C[i][j]==1) continue;
            is_down[i][j] = (is_down[i+1][j]|is_down[i][j+1]);
        }
    }
    int q;
    cin >> q;
    int xi, yi;
    bool keep;
    int ci, cj;
    for(int qr = 1; qr <= q; qr ++ ){
        cin >> xi >> yi;
        if(!is_up[xi][yi] || !is_down[xi][yi]){
            C[xi][yi]=1;
            cout << 1 << "\n";
        }
        else{
            keep = false;
            for(int i = xi - 1; i >= 1; i -- ){
                if(is_up[i][yi] && is_down[i][yi+1]){
                    keep = true;
                }
            }
            for(int i = yi - 1; i >= 1; i -- ){
                if(is_up[xi][i] && is_down[xi+1][i]){
                    keep = true;
                }
            }
            if(keep == true){
                C[xi][yi]=0;
                is_up[xi][yi]=false;
                is_down[xi][yi]=false;
                queue<pii> qq;
                qq.push(mp(xi,yi));
                while(!qq.empty()){
                    ci = qq.front().fi;
                    cj = qq.front().se;
                    qq.pop();
                    if(is_up[ci+1][cj] && !is_up[ci+1][cj-1]){
                        is_up[ci+1][cj]=false;
                        qq.push(mp(ci+1,cj));
                    }
                    if(is_up[ci][cj+1] && !is_up[ci-1][cj+1]){
                        is_up[ci][cj+1]=false;
                        qq.push(mp(ci,cj+1));
                    }
                }
                qq.push(mp(xi,yi));
                while(!qq.empty()){
                    ci = qq.front().fi;
                    cj = qq.front().se;
                    qq.pop();
                    if(is_down[ci-1][cj] && !is_down[ci-1][cj+1]){
                        is_down[ci-1][cj]=false;
                        qq.push(mp(ci-1,cj));
                    }
                    if(is_down[ci][cj-1] && !is_down[ci+1][cj-1]){
                        is_down[ci][cj-1]=false;
                        qq.push(mp(ci,cj-1));
                    }
                }
                cout << "1\n";
            }
            else{
                cout << "0\n";
            }
        }
    }
    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     freopen("in.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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