Submission #736809

#	Time	Username	Problem	Language	Result	Execution time	Memory
736809		flappybird	Gardening (RMI21_gardening)	C++17	100 / 100	19 ms	924 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define X 20
bool ispos(int N, int M, int K) {
	if (1ll * N * M > 200000) return false;
	if (N & 1) return false;
	if (M & 1) return false;
	N >>= 1;
	M >>= 1;
	if (N > M) swap(N, M);
	if (K == M + 1 && N == M) return false;
	if (K == N * M - 1) return false;
	return M <= K && K <= N * M;
}
vector<vector<int>> ans;
void solve(int N, int M, int K, int xpos, int ypos) {
	if (!K) return;
	if (M == 1 || N == 1) {
		if (M == 1) { for (int i = 0; i < N; i++) for (auto x : { i * 2, i * 2 + 1 }) for (auto y : { 0, 1 }) ans[xpos + x][ypos + y] = i + 1; }
		else { for (int i = 0; i < M; i++) for (auto x : { 0, 1 }) for (auto y : { 2 * i, 2 * i + 1 }) ans[xpos + x][ypos + y] = i + 1; }
		return;
	}
	if (ispos(N * 2 - 2, M * 2 - 2, K - 1)) {
		int i;
		for (i = 0; i < N * 2; i++) ans[xpos + i][ypos] = ans[xpos + i][ypos + M * 2 - 1] = K;
		for (i = 0; i < M * 2; i++) ans[xpos][ypos + i] = ans[xpos + N * 2 - 1][ypos + i] = K;
		solve(N - 1, M - 1, K - 1, xpos + 1, ypos + 1);
		return;
	}
	if (K >= M && ispos(N * 2 - 2, M * 2, K - M)) {
		for (int i = 0; i < M; i++) for (auto x : { 0, 1 }) for (auto y : { 2 * i, 2 * i + 1 }) ans[xpos + x][ypos + y] = K - i;
		solve(N - 1, M, K - M, xpos + 2, ypos);
		return;
	}
	if (K >= N && ispos(N * 2, M * 2 - 2, K - N)) {
		for (int i = 0; i < N; i++) for (auto x : { i * 2, i * 2 + 1 }) for (auto y : { 0, 1 }) ans[xpos + x][ypos + y] = K - i;
		solve(N, M - 1, K - N, xpos, ypos + 2);
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int N, M;
		ll K;
		cin >> N >> M >> K;
		if (!ispos(N, M, K)) {
			cout << "NO" << ln;
			continue;
		}
		ans = vector<vector<int>>(N, vector<int>(M));
		N >>= 1;
		M >>= 1;
		solve(N, M, K, 0, 0);
		cout << "YES" << ln;
		int i, j;
		for (i = 0; i < N * 2; i++) {
			for (j = 0; j < M * 2; j++) cout << ans[i][j] << bb;
			cout << ln;
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 39 / 39
• Subtask 6: 22 / 22