oj.uz

Submission #1037839

# Submission time Handle Problem Language Result Execution time Memory
1037839 2024-07-29T09:04:15 Z phong Furniture (JOI20_furniture) C++17
0 / 100
 1 ms 2652 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 1e3 + 5, N = 1e5;
const ll oo = 1e18;
const int lg = 19, M = 2, mod = 1e6;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;

int n, m;
bool a[nmax][nmax];
bool R[nmax][nmax], L[nmax][nmax], B[nmax][nmax];
int cnt[nmax * 2];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> a[i][j];
        }
    }
    L[1][1] = R[n][m] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(!a[i][j]){
                L[i][j] |= L[i - 1][j] | L[i][j - 1];
            }
        }
    }
    for(int i = n; i >= 1; --i){
        for(int j = m; j >= 1; --j){
            if(!a[i][j]){
                R[i][j] |= R[i + 1][j] | R[i][j + 1];
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            B[i][j] = L[i][j] | R[i][j];
            if(B[i][j]) cnt[i + j]++;
        }
    }
    int q;cin >> q;
    queue<pii> one;
    while(q--){
        int x, y;
        cin >> x >> y;
        if(!B[x][y]) cout << 1 << endl;
        else{
            cout << (cnt[x + y] > 1) << endl;
            if(cnt[x + y] > 1){
                one.push({x, y});
                B[x][y] = 0;
                while(one.size()){
                    pii tmp = one.front();one.pop();
                    int i = tmp.fi, j = tmp.se;
                    cnt[i + j]--;
                    if(B[i - 1][j] && !B[i - 1][j + 1]){
                        one.push({i - 1, j});
                        B[i - 1][j] = 0;
                    }
                    if(B[i][j - 1] && !B[i + 1][j - 1]){
                        one.push({i, j - 1});
                        B[i][j - 1] = 0;
                    }
                    if(B[i + 1][j] && !B[i + 1][j - 1]){
                        one.push({i + 1, j});
                        B[i + 1][j] = 0;
                    }
                    if(B[i][j + 1] && !B[i - 1][j + 1]){
                        one.push({i, j + 1});
                        B[i][j + 1] = 0;
                    }
                }
            }
            else cnt[x + y] = 0;
        }
    }
}
/*


*/

Compilation message

furniture.cpp:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | main(){
      | ^~~~

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -