oj.uz

Submission #997428

# Submission time Handle Problem Language Result Execution time Memory
997428 2024-06-12T09:58:27 Z DanielPr8 Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 34788 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 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 600 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 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 600 KB Output is correct
6 Correct 2 ms 580 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 8 ms 1756 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 128 ms 9100 KB Output is correct
13 Correct 55 ms 11452 KB Output is correct
14 Correct 163 ms 15020 KB Output is correct
15 Correct 163 ms 10748 KB Output is correct
16 Execution timed out 5029 ms 34788 KB Time limit exceeded
17 Halted 0 ms 0 KB -