oj.uz

답안 #1037853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1037853 2024-07-29T09:15:18 Z phong Furniture (JOI20_furniture) C++17
100 / 100
 189 ms 16008 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;
                    }
                }
            }
        }
    }
}
/*
4 3
0 1 1
1 1 0
0 0 0
0 0 0
5
2 2
1 3
3 2
4 3
1 3


*/

Compilation message

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 3 ms 2652 KB Output is correct
8 Correct 2 ms 2652 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 6 ms 2940 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 108 ms 8824 KB Output is correct
13 Correct 41 ms 6012 KB Output is correct
14 Correct 152 ms 13652 KB Output is correct
15 Correct 170 ms 14040 KB Output is correct
16 Correct 166 ms 14872 KB Output is correct
17 Correct 182 ms 15444 KB Output is correct
18 Correct 174 ms 15228 KB Output is correct
19 Correct 177 ms 15956 KB Output is correct
20 Correct 171 ms 15856 KB Output is correct
21 Correct 189 ms 16008 KB Output is correct