Submission #997428

#	Time	Username	Problem	Language	Result	Execution time	Memory
997428		DanielPr8	Furniture (JOI20_furniture)	C++14	5 / 100	5029 ms	34788 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vvb fur;
ll n, m;
vll sr, sc;

bool fu(ll i, ll j){
    if(i<0 || i>=n || j<0 || j>=m)return 1;
    else return fur[i][j];
}
bool pufu(ll i, ll j, bool c, vpl& pa){
    bool d = 0;
    if(i==0 && j==0)return 0;
    if(i==n-1 && j==m-1)return 0;
    if(i<0 || i>=n || j<0 || j>=m)return 0;
    if(fu(i, j))return 0;
    if(c || ((fu(i+1,j)&&fu(i,j+1)) || (fu(i-1,j)&&fu(i,j-1)))){
        fur[i][j]=1;
        pa.pb({i,j});
        sr[i]--;
        sc[j]--;
        if(sr[i]==0||sc[j]==0)return 1;
        d |= pufu(i+1,j,0,pa);
        d |= pufu(i-1,j,0,pa);
        d |= pufu(i,j+1,0,pa);
        d |= pufu(i,j-1,0,pa);
    }
    return d;
}
void rev(vpl& pas){
    for(auto [a,b]:pas){
        fur[a][b]=0;
        sr[a]++;
        sc[b]++;
    }
    pas.clear();
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    cin >> n >> m;
    sr = vll(n,m);
    sc = vll(m,n);
    fur = vvb(n, vb(m));
    bool c;
    vpl pa;
    for(ll i = 0; i < n; ++i){
        for(ll j = 0; j < m; ++j){
            cin >> c;
            if(c==1)pufu(i, j, 1,pa);
        }
    }

    ll q, a, b;
    cin >> q;
    while(q--){
        cin >> a >> b;
        a--;b--;
        if(fu(a,b)){
            cout << "1\n";
            continue;
        }
        else{
            vpl pas = {};
            if(pufu(a,b, 1, pas)){
                cout << "0\n";
                rev(pas);
            }
            else{
                cout << "1\n";
                pas.clear();
            }

        }
    }
}

Compilation message (stderr)

furniture.cpp: In function 'void rev(vpl&)':
furniture.cpp:43:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto [a,b]:pas){
      |              ^

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