oj.uz

Submission #790158

# Submission time Handle Problem Language Result Execution time Memory
790158 2023-07-22T11:24:27 Z vjudge1 Furniture (JOI20_furniture) C++17
100 / 100
 273 ms 19780 KB 
//i_love_aisukiuwu
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
	#include "/home/trucmai/.vim/tools.h"
	#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
	#else
	#define debug(x...)
#endif

void open(){
  if(fopen("i.inp","r")){
    freopen("i.inp","r",stdin);
    freopen("o.out","w",stdout);
  }
}

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN1 = 1e6 + 5,MN2 = 1e3 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n,m,c[MN2][MN2],place[MN1];
ll dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};

bool check(ll x,ll y){
  if((x == 1 && y == 1) || (x == n && y == m)) return false; 
  if((x==n || c[x+1][y]) && (y==m || c[x][y+1])) return true;
  if((x== 1 || c[x-1][y]) && (y==1 || c[x][y-1])) return true; 
  return false;
}

void bfs(ll u,ll v){
  c[u][v] = true; place[u+v]--;
  for(ll i = 0;i < 4;++i){
    ll x = u + dx[i],y = v + dy[i]; 
    if(min(x,y) <= 0 || x > n || y > m || c[x][y]) continue; 
    if(check(x,y)) bfs(x,y);
  }
}

void solve(){
  cin>>n>>m;
  for(ll i = 1;i <= n;++i)
    for(ll j = 1;j <= m;++j){
      place[i+j]++;
      if(c[i][j]){ll tmp; cin>>tmp; continue;}
      cin>>c[i][j]; 
      if(c[i][j]) bfs(i,j);
    } 
  ll q; cin>>q;
  while(q--){ 
    ll x,y; cin>>x>>y;
    if(c[x][y]) cout<<1<<endl; 
    else if(place[x + y]==1) cout<<0<<endl; 
    else{
      bfs(x,y);
      cout<<1<<endl; 
    }
  }
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
  open();
  ll t = 1; //cin>>t;
  while(t--) solve(); 
  
  #ifdef LOCAL
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  #endif
}

Compilation message

furniture.cpp: In function 'void open()':
furniture.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("i.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
furniture.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("o.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 3 ms 856 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 720 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 3 ms 852 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 8 ms 1108 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 125 ms 12716 KB Output is correct
13 Correct 46 ms 9696 KB Output is correct
14 Correct 194 ms 17196 KB Output is correct
15 Correct 211 ms 17344 KB Output is correct
16 Correct 208 ms 18440 KB Output is correct
17 Correct 245 ms 19300 KB Output is correct
18 Correct 273 ms 18756 KB Output is correct
19 Correct 232 ms 19740 KB Output is correct
20 Correct 212 ms 19732 KB Output is correct
21 Correct 219 ms 19780 KB Output is correct