oj.uz

Submission #637760

# Submission time Handle Problem Language Result Execution time Memory
637760 2022-09-03T07:13:14 Z Karliver Furniture (JOI20_furniture) C++17
100 / 100
 244 ms 13984 KB 
	
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
#define ff first
#define se second
#define mp make_pair
using ll = long long;
int MOD = 998244353;
const int INF = 1e9 + 1;
const int N = 1001;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
    return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
    return (x > y ? x = y, 1 : 0);
}



void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)

bool b1[N][N], b2[N][N];
int n, m;
int cnt[2 * N];

void block1(int i, int j) {
	cnt[i + j] -= !b2[i][j];
	b1[i][j] = 1;
	if(i < n - 1 && !b1[i+1][j] && (j == 0 || b1[i+1][j-1]))
		block1(i+1, j);
	if(j < m - 1 && !b1[i][j+1] && (i == 0 || b1[i-1][j+1]))
		block1(i, j+1);
}
void block2(int i, int j) {
	cnt[i + j] -= !b1[i][j];
	b2[i][j] = 1;
	if(i > 0 && !b2[i-1][j] && (j == m - 1 || b2[i-1][j+1]))
		block2(i-1, j);
	if(j > 0 && !b2[i][j-1] && (i == n - 1 || b2[i+1][j-1]))
		block2(i, j - 1);
}
void solve() {
		

	cin >> n >> m;
	
	forn(i, n) forn(j, m) {
		int x;
		cin >> x;
		
		if(x == 1) {
			if(!b1[i][j]) block1(i, j);
			if(!b2[i][j]) block2(i, j);
		}
		cnt[i + j] += 1;
	}
	int q;
	cin >> q;
	
	while(q--) {
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		
		if(b1[x][y] || b2[x][y]) {
			cout << 1 << '\n';
		}
		else if(cnt[x + y] > 1) {
			cout << 1 << '\n';
			block1(x, y);
			block2(x, y);
		}
		else cout << 0 << '\n';
	}
	
	
	
}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 544 KB Output is correct
9 Correct 5 ms 596 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 544 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 117 ms 6880 KB Output is correct
13 Correct 47 ms 4044 KB Output is correct
14 Correct 205 ms 11592 KB Output is correct
15 Correct 214 ms 11944 KB Output is correct
16 Correct 211 ms 12944 KB Output is correct
17 Correct 221 ms 13504 KB Output is correct
18 Correct 241 ms 13240 KB Output is correct
19 Correct 242 ms 13952 KB Output is correct
20 Correct 236 ms 13868 KB Output is correct
21 Correct 244 ms 13984 KB Output is correct