oj.uz

Submission #990034

# Submission time Handle Problem Language Result Execution time Memory
990034 2024-05-29T11:43:53 Z AlperenT_ Furniture (JOI20_furniture) C++17
0 / 100
 5000 ms 2396 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =2000+10  ,  N = 1e5 +1 , lg = 20 , maxq = 202   , inf = 1e18  , maxk = 2022  , mod =998244353;
int mark[maxn][maxn] , v[maxn] , n, m ;

int ch(int a ,int b){
    if(mark[a-1][b] == 0 && mark[a][b-1] == 0 && (!(a==1 && b==1)))return 1 ;
    if(mark[a+1][b] == 0 && mark[a][b+1] == 0 && (!(a==n&&b==m)))return 1; 
    return 0 ;
}
int dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , -1 , 1}; 

void upd(int x, int y){
    mark[x][y] =0 ;
    v[x+y]--;
    rep(i , 0 , 3){
        int a= x+dx[i] , b = y+dy[i] ;
        if(mark[a][b] == 1 && ch(a,b) == 1){
            upd(a,b) ;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m ;
    vector <pii> vec; 
    rep(i ,1 ,n){
        rep(j ,1 ,m){
            char a ;
            cin >> a;
            if(a=='1')vec.pb({i,j});
            v[i+j] ++ ;
            mark[i][j] = 1 ;
        }
    }
    for(auto [i,j] : vec)upd(i , j);
    rep(i , 2 ,n+m){
        if(v[i] ==0 )while(1){}
    }
    int q; 
    cin >> q ;
    while(q--){
        int x, y ;
        cin >> x >> y; 
        if(mark[x][y] == 0){
            cout << "1\n";
            continue ;
        }
        if(v[x+y]==1){
            cout << "0\n";
            continue ;
        }
        upd(x,y) ;
        cout << "1\n";
    }
}

/*

*/

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Execution timed out 5033 ms 2396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Execution timed out 5033 ms 2396 KB Time limit exceeded
3 Halted 0 ms 0 KB -