oj.uz

Submission #342279

# Submission time Handle Problem Language Result Execution time Memory
342279 2021-01-01T17:34:22 Z ryansee Furniture (JOI20_furniture) C++14
100 / 100
 515 ms 20984 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (1006)
ll n,m,q,cnt[MAXN*2],R[MAXN][MAXN];
bool A[MAXN][MAXN];
bool dp(ll x,ll y) {
	if(x > n || y > m || A[x][y]) return 0;
	if(~R[x][y]) return R[x][y];
	return R[x][y] = dp(x+1, y) | dp(x, y+1);
}
void gg(ll x,ll y) {
	if(R[x][y]==0) return;
	-- cnt[x+y], R[x][y] = 0;
}
bool chk(ll x,ll y) {
	return x >= 1 && y >= 1 && x <= n && y <= m && R[x][y];
}
void bck(ll x,ll y) {
	if(x < 1 || y < 1 || R[x][y] == 0) return;
	if(chk(x+1, y) || chk(x, y+1)) return;
	gg(x, y);
	bck(x-1, y), bck(x, y-1);
}
void bck2(ll x,ll y) {
	if(x > n || y > m || R[x][y] == 0) return;
	if(chk(x-1, y) || chk(x, y-1)) return;
	gg(x, y);
	bck2(x+1, y), bck2(x, y+1);
}
int main() {
	mmst(R,-1);
	FAST
	cin>>n>>m;
	FOR(i,1,n)FOR(j,1,m)cin>>A[i][j];
	R[n][m]=1;
	dp(1, 1);
	FOR(i,1,n)FOR(j,1,m)if(R[i][j]==-1)R[i][j]=0;else if(R[i][j])++cnt[i+j];
	cin>>q;
	while(q--){
		ll x, y;
		cin>>x>>y;
		if(R[x][y] == 1 && cnt[x+y]==1) {
			cout<<0<<'\n';
			continue;
		}
		cout<<1<<'\n';
		gg(x, y);
		bck(x-1, y), bck(x, y-1);
		bck2(x+1, y), bck2(x, y+1);
	}
}

Compilation message

furniture.cpp: In function 'bool dp(ll, ll)':
furniture.cpp:34:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   34 |  return R[x][y] = dp(x+1, y) | dp(x, y+1);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8300 KB Output is correct
2 Correct 6 ms 8428 KB Output is correct
3 Correct 7 ms 8428 KB Output is correct
4 Correct 8 ms 8428 KB Output is correct
5 Correct 8 ms 8428 KB Output is correct
6 Correct 8 ms 8556 KB Output is correct
7 Correct 9 ms 8556 KB Output is correct
8 Correct 8 ms 8556 KB Output is correct
9 Correct 8 ms 8556 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8300 KB Output is correct
2 Correct 6 ms 8428 KB Output is correct
3 Correct 7 ms 8428 KB Output is correct
4 Correct 8 ms 8428 KB Output is correct
5 Correct 8 ms 8428 KB Output is correct
6 Correct 8 ms 8556 KB Output is correct
7 Correct 9 ms 8556 KB Output is correct
8 Correct 8 ms 8556 KB Output is correct
9 Correct 8 ms 8556 KB Output is correct
10 Correct 15 ms 8684 KB Output is correct
11 Correct 7 ms 8428 KB Output is correct
12 Correct 226 ms 14060 KB Output is correct
13 Correct 88 ms 11116 KB Output is correct
14 Correct 431 ms 19180 KB Output is correct
15 Correct 447 ms 19116 KB Output is correct
16 Correct 481 ms 20204 KB Output is correct
17 Correct 515 ms 20716 KB Output is correct
18 Correct 440 ms 20332 KB Output is correct
19 Correct 426 ms 20984 KB Output is correct
20 Correct 368 ms 20972 KB Output is correct
21 Correct 441 ms 20972 KB Output is correct