Submission #761453

#	Time	Username	Problem	Language	Result	Execution time	Memory
761453		US3RN4M3	Gardening (RMI21_gardening)	C++17	5 / 100	78 ms	568 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int arr[200000];

ll w, h;
int col;

inline int & get(int x, int y) {
	return arr[x*h + y];
}

pair<ll, ll> possible_range(ll n, ll m) {
	return {max(n, m) / 2, (n * m) / 4};
}

bool fits(ll n, ll m, ll k) {
	pair<ll, ll> range = possible_range(n, m);
	return (range.first <= k && k <= range.second);
}

void create_rect(ll sx, ll sy, ll n, ll m, ll k) {
	//cout << sx << " " << sy << " " << n << " " << m << " " << k << endl;
	if(n == 2 || m == 2) {
		assert(k == (m * n) / 4);
		for(int i = 0; i < n; i += 2) for(int j = 0; j < m; j += 2) {
			col++;
			get(sx + i, sy + j) = col;
			get(sx + i + 1, sy + j) = col;
			get(sx + i, sy + j + 1) = col;
			get(sx + i + 1, sy + j + 1) = col;
		}
		return;
	}
	if(n != 2 && m != 2 && fits(n - 2, m - 2, k - 1)) {
		col++;
		for(int i = 0; i < n; i++) {
			get(sx + i, sy) = col;
			get(sx + i, sy + m - 1) = col;
		}
		for(int i = 0; i < m; i++) {
			get(sx, sy + i) = col;
			get(sx + n - 1, sy + i) = col;
		}
		return create_rect(sx + 1, sy + 1, n - 2, m - 2, k - 1);
	}
	if(n != 2 && fits(n - 2, m, k - (m / 2))) {
		for(int i = 0; i < m; i += 2) {
			col++;
			get(sx, sy + i) = col;
			get(sx + 1, sy + i) = col;
			get(sx, sy + i + 1) = col;
			get(sx + 1, sy + i + 1) = col;
		}
		return create_rect(sx + 2, sy, n - 2, m, k - (m / 2));
	}
	if(m != 2 && fits(n, m - 2, k - (n / 2))) {
		for(int i = 0; i < n; i += 2) {
			col++;
			get(sx + i, sy) = col;
			get(sx + i, sy + 1) = col;
			get(sx + i + 1, sy) = col;
			get(sx + i + 1, sy + 1) = col;
		}
		return create_rect(sx, sy + 2, n, m - 2, k - (n / 2));
	}
}


void solve() {
	ll k;
	cin >> w >> h >> k;
	if(w * h > 200000 || w & 1 || h & 1) {
		cout << "NO" << endl;
		return;
	}
	if((w * h) % 8 != (4 * k) % 8) {
		cout << "NO" << endl;
		return;
	}
	ll lower = max(w, h) / 2;
	ll upper = (w * h) / 4;
	if(k < lower || k > upper) {
		cout << "NO" << endl;
		return;
	}
	col = 0;
	create_rect(0, 0, w, h, k);
	cout << "YES" << endl;
	for(int i = 0; i < w; i++) for(int j = 0; j < h; j++) cout << get(i, j) << " \n"[j == h - 1];
}

main() {
	int t; cin >> t;
	while(t--)
		solve();
}

Compilation message (stderr)

Main.cpp:94:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   94 | main() {
      | ^~~~

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