oj.uz

Submission #962447

# Submission time Handle Problem Language Result Execution time Memory
962447 2024-04-13T14:34:22 Z Pring Furniture (JOI20_furniture) C++17
100 / 100
 219 ms 12236 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } 
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 1005;
int n, m, q, br;
bitset<MXN> b[MXN];
int cnt[MXN * 2];

void PRE() {
	FOR(i, 0, n + 2) FOR(j, 0, m + 2) if (b[i][j] == 0) cnt[i + j]++;
}

bool PUT(int x, int y) {
	if (b[x][y]) return true;
	if (cnt[x + y] == 1) return false;
	b[x][y] = 1;
	cnt[x + y]--;
	queue<pii> q;
	q.push(mp(x + 1, y));
	q.push(mp(x, y + 1));
	while (q.size()) {
		auto [xx, yy] = q.front();
		q.pop();
		debug(xx, yy, 1);
		if (b[xx][yy] == 1) continue;
		if (!b[xx - 1][yy] || !b[xx][yy - 1]) continue;
		b[xx][yy] = 1;
		cnt[xx + yy]--;
		q.push(mp(xx + 1, yy));
		q.push(mp(xx, yy + 1));
	}
	q.push(mp(x - 1, y));
	q.push(mp(x, y - 1));
	while (q.size()) {
		auto [xx, yy] = q.front();
		q.pop();
		debug(xx, yy);
		if (b[xx][yy] == 1) continue;
		if (!b[xx + 1][yy] || !b[xx][yy + 1]) continue;
		b[xx][yy] = 1;
		cnt[xx + yy]--;
		q.push(mp(xx - 1, yy));
		q.push(mp(xx, yy - 1));
	}
	return true;
}

void miku() {
	cin >> n >> m;
	b[0].set();
	b[n + 1].set();
	FOR(i, 1, n + 1) {
		b[i][0] = true;
		b[i][m + 1] = true;
	}
	PRE();
	FOR(i, 1, n + 1) FOR(j, 1, m + 1) {
		cin >> br;
		if (br) PUT(i, j);
	}
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		debug(x, y);
		cout << PUT(x, y) << '\n';
	}
}

int32_t main() {
	cin.tie(0) -> sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	miku();
	return 0;
}

Compilation message

furniture.cpp: In function 'bool PUT(int, int)':
furniture.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
furniture.cpp:41:3: note: in expansion of macro 'debug'
   41 |   debug(xx, yy, 1);
      |   ^~~~~
furniture.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
furniture.cpp:54:3: note: in expansion of macro 'debug'
   54 |   debug(xx, yy);
      |   ^~~~~
furniture.cpp: In function 'void miku()':
furniture.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
furniture.cpp:82:3: note: in expansion of macro 'debug'
   82 |   debug(x, y);
      |   ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 592 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 592 KB Output is correct
10 Correct 10 ms 604 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 123 ms 4952 KB Output is correct
13 Correct 55 ms 2368 KB Output is correct
14 Correct 213 ms 9952 KB Output is correct
15 Correct 198 ms 10080 KB Output is correct
16 Correct 194 ms 11092 KB Output is correct
17 Correct 207 ms 11604 KB Output is correct
18 Correct 211 ms 11344 KB Output is correct
19 Correct 207 ms 12020 KB Output is correct
20 Correct 219 ms 12116 KB Output is correct
21 Correct 211 ms 12236 KB Output is correct