Submission #527925

#	Time	Username	Problem	Language	Result	Execution time	Memory
527925		GioChkhaidze	Gardening (RMI21_gardening)	C++14	100 / 100	30 ms	5580 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;

const int N = 2e5 + 5;

int col = 0;
vector < int > ans[N];

inline pair < int , int > get(int n, int m) {
	assert(n % 2 == 0);
	assert(m % 2 == 0);
	if (n == 0 || m == 0) return {0, 0};
	return {max(n, m) / 2, n * m / 4};
}

vector < pair < int , int > > c2;
vector < pair < pair < int , int > , pair < int , int > > > car;

inline void solve(int x, int y, int k, int lenx, int leny) {
	if (!k || !lenx || !leny) return;
	if (lenx > 2 && leny > 2) {
		int newk = k - 1;
		pair < int , int > lim = get(lenx - 2, leny - 2);	
		if (lim.f <= newk && newk <= lim.s && newk != lim.s - 1) {
			if (!(lenx == leny && newk == lim.f + 1)) {
				car.pb({{x, y}, {x + lenx - 1, y + leny - 1}});
				solve(x + 1, y + 1, newk, lenx - 2, leny - 2);
				return;
			}
		}
	}
	
	if (lenx >= 2) {
		int newk = k - leny / 2;
		pair < int , int > lim = get(lenx - 2, leny);
		if (lim.f <= newk && newk <= lim.s && newk != lim.s - 1) {
			if (!(lenx - 2 == leny && newk == lim.f + 1)) {
				for (int j = y; j < y + leny; j += 2) 
					c2.pb({x, j});
				solve(x + 2, y, newk, lenx - 2, leny);
				return ;
			}
		}
	}
	
	if (leny >= 2) {
		int newk = k - lenx / 2;
		pair < int , int > lim = get(lenx, leny - 2);
		if (lim.f <= newk && newk <= lim.s && newk != lim.s - 1) {
			if (!(lenx == leny - 2 && newk == lim.f + 1)) {	
				for (int i = x; i < x + lenx; i += 2) 
					c2.pb({i, y});
				solve(x, y + 2, newk, lenx, leny - 2);
				return ;
			}
		}
	}
	
	for (int i = 4; i <= lenx / 2; i += 2) {
		pair < int , int > liml = get(i, leny);
		pair < int , int > limr = get(lenx - i, leny);
		
		int kl = k - limr.s, kr = limr.s;
		if (liml.f <= kl && kl <= liml.s && kl != liml.s - 1) {
			if (!(i == leny && kl == liml.f + 1)) {
				solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
				return ;
			}
		}
		kl = liml.s, kr = k - liml.s;
		if (limr.f <= kr && kr <= limr.s && kr != limr.s - 1) {
			if (!(lenx - i == leny && kr == limr.f + 1)) {
				solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
				return ;
			}
		}
		
		kl = k - limr.f, kr = limr.f;
		if (liml.f <= kl && kl <= liml.s && kl != liml.s - 1) {
			if (!(i == leny && kl == liml.f + 1)) {
				solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
				return ;
			}
		}
		kl = liml.f, kr = k - liml.f;
		if (limr.f <= kr && kr <= limr.s && kr != limr.s - 1) {
			if (!(lenx - i == leny && kr == limr.f + 1)) {
				solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
				return ;
			}
		}
		
		liml.s -= 2;
		limr.s -= 2;
		if (i == leny) liml.f += 2;
		if (lenx - i == leny) limr.f += 2;	
	
		int l = liml.f, r = liml.s, mid, res = -1;
		while (l <= r) {
			mid = (l + r) / 2;
			if (k - mid <= limr.s) {
				res = k, r = mid - 1;
			}
				else {
				l = mid + 1;		
			}
		}
		
		if (res == -1) continue;
		kl = res, kr = k - res;
		if (liml.f <= kl && kl <= liml.s && limr.f <= kr && kr <= limr.s) {
			solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
			return ;
		}
	}
}

inline void solve() {
	int n, m, k;
	col = 0;
	cin >> n >> m >> k;
	if (n == m && k == max(n, m) / 2 + 1) {
		cout << "NO\n";
		return ;
	}
	
	if (n % 2 || m % 2 || 2 * k < max(n, m) || n * m < 4 * k || k == n * m / 4 - 1) {
		cout << "NO\n";
		return ;
	}
	
	c2.clear();
	car.clear();
	solve(1, 1, k, n, m);
	int ans[n + 10][m + 10];
	for (int t = 0; t < c2.size(); ++t) {
		++col;
		int x = c2[t].f, y = c2[t].s;
		for (int i = x; i < x + 2; ++i)
			for (int j = y; j < y + 2; ++j) 
				ans[i][j] = col;
	}
	
	for (int t = 0; t < car.size(); ++t) {
		++col;
		int x = car[t].f.f, y = car[t].f.s;
		int X = car[t].s.f, Y = car[t].s.s;
		for (int i = x; i <= X; ++i) {
			ans[i][y] = ans[i][Y] = col;
		}
		for (int j = y; j <= Y; ++j) {
			ans[x][j] = ans[X][j] = col;
		}
	}

	cout << "YES\n";	
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) 
			cout << ans[i][j] << " ";
		cout << "\n";
	}
}

main () { 
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |  for (int t = 0; t < c2.size(); ++t) {
      |                  ~~^~~~~~~~~~~
Main.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  for (int t = 0; t < car.size(); ++t) {
      |                  ~~^~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:167:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  167 | main () {
      | ^~~~

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