oj.uz

Submission #503190

# Submission time Handle Problem Language Result Execution time Memory
503190 2022-01-07T13:09:52 Z atoiz Gardening (RMI21_gardening) C++14
100 / 100
 24 ms 860 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <cassert>

using namespace std;

const int SMALL = 20;
bitset<SMALL * SMALL> small_prep[SMALL][SMALL];

void prep() {
	small_prep[2][2][1] = 1;
	for (int a = 2; a <= SMALL; a += 2) {
		for (int b = 2; b <= SMALL; b += 2) {
			if (a > b) { small_prep[a][b] = small_prep[b][a]; continue; }
			small_prep[a][b] |= small_prep[a - 2][b - 2] << 1;

			for (int c = 2; c < a; c += 2) {
				for (int x = 0; x < SMALL * SMALL; ++x) if (small_prep[c][b][x]) {
					small_prep[a][b] |= small_prep[a - c][b] << x;
				}
			}

			for (int c = 2; c < b; c += 2) {
				for (int x = 0; x < SMALL * SMALL; ++x) if (small_prep[a][c][x]) {
					small_prep[a][b] |= small_prep[a][b - c] << x;
				}
			}
		}
	}
}

bool check(int a, int b, int x) {
	if (a > b) return check(b, a, x);
	if (b < SMALL) return small_prep[a][b][x];
	if (a == 0) return x == 0;
	if (a == 2) return x == b / 2;
	if (x > (a / 2) * (b / 2)) return false;
	if (x == (a / 2) * (b / 2) - 1) return false;
	if (x < b / 2) return false;
	if (a == b && x == b / 2 + 1) return false;
	return true;
}

void solve(vector<vector<int>> &arr, int x0, int y0, int a, int b, int x, int &nxt) {
	assert(check(a, b, x));

	if (x == 1) {
		for (int i = 0; i < 2; ++i) {
			for (int j = 0; j < 2; ++j) {
				arr[x0 + i][y0 + j] = nxt;
			}
		}
		++nxt;
		return;
	}

	if (check(a - 2, b - 2, x - 1)) {
		for (int i = 0; i < a; ++i) arr[x0 + i][y0] = arr[x0 + i][y0 + b - 1] = nxt;
		for (int j = 0; j < b; ++j) arr[x0][y0 + j] = arr[x0 + a - 1][y0 + j] = nxt;
		++nxt;
		solve(arr, x0 + 1, y0 + 1, a - 2, b - 2, x - 1, nxt);
		return;
	}

	static auto lb = [](int a, int b) { return max(a, b) / 2; };
	static auto ub = [](int a, int b) { return (a / 2) * (b / 2); };

	for (int c = 2; c < a; c += 2) {
		for (int y = max(lb(c, b), x - ub(a - c, b)); y <= min(ub(c, b), x - lb(a - c, b)); ++y) {
			if (check(c, b, y) && check(a - c, b, x - y)) {
				return solve(arr, x0, y0, c, b, y, nxt), solve(arr, x0 + c, y0, a - c, b, x - y, nxt);
			}
		}
	}

	for (int c = 2; c < b; c += 2) {
		for (int y = max(lb(a, c), x - ub(a, b - c)); y <= min(ub(a, c), x - lb(a, b - c)); ++y) {
			if (check(a, c, y) && check(a, b - c, x - y)) {
				return solve(arr, x0, y0, a, c, y, nxt), solve(arr, x0, y0 + c, a, b - c, x - y, nxt);
			}
		}
	}

	assert(false);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	prep();
	int t; cin >> t;
	while (t--) {
		int a, b, x; cin >> a >> b >> x;
		if (!check(a, b, x)) cout << "NO\n";
		else {
			vector<vector<int>> arr(a, vector<int>(b));
			int nxt = 1;
			solve(arr, 0, 0, a, b, x, nxt);
			cout << "YES\n";
			for (auto v : arr) {
				for (auto w : v) {
					cout << w << ' ';
				}
				cout << '\n';
			}
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 720 KB Correct! Azusa and Laika like the garden :)

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 720 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)
3 Correct 10 ms 600 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 720 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)
3 Correct 10 ms 600 KB Correct! Azusa and Laika like the garden :)
4 Correct 14 ms 660 KB Correct! Azusa and Laika like the garden :)
5 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
2 Correct 9 ms 640 KB Correct! Azusa and Laika like the garden :)
3 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
4 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)
5 Correct 9 ms 648 KB Correct! Azusa and Laika like the garden :)
6 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
7 Correct 9 ms 652 KB Correct! Azusa and Laika like the garden :)
8 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)
9 Correct 9 ms 624 KB Correct! Azusa and Laika like the garden :)
10 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
11 Correct 13 ms 688 KB Correct! Azusa and Laika like the garden :)
12 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
13 Correct 9 ms 580 KB Correct! Azusa and Laika like the garden :)

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
2 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
3 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
4 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
5 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
6 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
7 Correct 5 ms 464 KB Correct! Azusa and Laika like the garden :)
8 Correct 4 ms 464 KB Correct! Azusa and Laika like the garden :)
9 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
10 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
11 Correct 3 ms 332 KB Correct! Azusa and Laika like the garden :)
12 Correct 4 ms 464 KB Correct! Azusa and Laika like the garden :)
13 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
14 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
15 Correct 3 ms 468 KB Correct! Azusa and Laika like the garden :)
16 Correct 4 ms 464 KB Correct! Azusa and Laika like the garden :)
17 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 720 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)
3 Correct 10 ms 600 KB Correct! Azusa and Laika like the garden :)
4 Correct 14 ms 660 KB Correct! Azusa and Laika like the garden :)
5 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)
6 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
7 Correct 9 ms 640 KB Correct! Azusa and Laika like the garden :)
8 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
9 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)
10 Correct 9 ms 648 KB Correct! Azusa and Laika like the garden :)
11 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
12 Correct 9 ms 652 KB Correct! Azusa and Laika like the garden :)
13 Correct 10 ms 588 KB Correct! Azusa and Laika like the garden :)
14 Correct 9 ms 624 KB Correct! Azusa and Laika like the garden :)
15 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
16 Correct 13 ms 688 KB Correct! Azusa and Laika like the garden :)
17 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
18 Correct 9 ms 580 KB Correct! Azusa and Laika like the garden :)
19 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
20 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
21 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
22 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
23 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
24 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
25 Correct 5 ms 464 KB Correct! Azusa and Laika like the garden :)
26 Correct 4 ms 464 KB Correct! Azusa and Laika like the garden :)
27 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
28 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
29 Correct 3 ms 332 KB Correct! Azusa and Laika like the garden :)
30 Correct 4 ms 464 KB Correct! Azusa and Laika like the garden :)
31 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
32 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
33 Correct 3 ms 468 KB Correct! Azusa and Laika like the garden :)
34 Correct 4 ms 464 KB Correct! Azusa and Laika like the garden :)
35 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
36 Correct 17 ms 704 KB Correct! Azusa and Laika like the garden :)
37 Correct 13 ms 720 KB Correct! Azusa and Laika like the garden :)
38 Correct 12 ms 752 KB Correct! Azusa and Laika like the garden :)
39 Correct 13 ms 856 KB Correct! Azusa and Laika like the garden :)
40 Correct 13 ms 704 KB Correct! Azusa and Laika like the garden :)
41 Correct 15 ms 720 KB Correct! Azusa and Laika like the garden :)
42 Correct 12 ms 720 KB Correct! Azusa and Laika like the garden :)
43 Correct 13 ms 848 KB Correct! Azusa and Laika like the garden :)
44 Correct 13 ms 736 KB Correct! Azusa and Laika like the garden :)
45 Correct 12 ms 720 KB Correct! Azusa and Laika like the garden :)
46 Correct 13 ms 812 KB Correct! Azusa and Laika like the garden :)
47 Correct 13 ms 776 KB Correct! Azusa and Laika like the garden :)
48 Correct 13 ms 816 KB Correct! Azusa and Laika like the garden :)
49 Correct 13 ms 712 KB Correct! Azusa and Laika like the garden :)
50 Correct 13 ms 808 KB Correct! Azusa and Laika like the garden :)
51 Correct 12 ms 708 KB Correct! Azusa and Laika like the garden :)
52 Correct 13 ms 716 KB Correct! Azusa and Laika like the garden :)
53 Correct 14 ms 860 KB Correct! Azusa and Laika like the garden :)
54 Correct 13 ms 844 KB Correct! Azusa and Laika like the garden :)
55 Correct 13 ms 716 KB Correct! Azusa and Laika like the garden :)
56 Correct 13 ms 716 KB Correct! Azusa and Laika like the garden :)
57 Correct 13 ms 720 KB Correct! Azusa and Laika like the garden :)
58 Correct 13 ms 716 KB Correct! Azusa and Laika like the garden :)
59 Correct 14 ms 728 KB Correct! Azusa and Laika like the garden :)
60 Correct 14 ms 836 KB Correct! Azusa and Laika like the garden :)