Submission #1136537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136537		dadas08	Gardening (RMI21_gardening)	C++20	11 / 100	38 ms	832 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
void _main();
int main() {
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	_main();
	return 0;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vl = std::vector<ll>;
using vii = std::vector<pair<int, int> >;
using vvl = std::vector<vl>;
using vll = std::vector<pair<ll , ll> >;
using vd = std::vector<double>;
using vvd = std::vector<vd>;
using vs = std::vector<std::string>;
using vvs = std::vector<vs>;
using vb = std::vector<bool>;
using vvb = std::vector<vb>;
using vc = std::vector<char>;
using vvc = std::vector<vc>;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
using piil = std::pair<pair<int, int>, ll>;
using mii = std::map<int, int>;
using mll = std::map<ll, ll>;
using pql = std::priority_queue<ll>;
using pqi = std::priority_queue<int>;
using pqiil = std::priority_queue<pair<pair<int, int>, ll> >;
using pqii = std::priority_queue<pair<int, int> >;

#define pb push_back
#define ps push
#define eb emplace_back
#define is insert
#define er erase
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define sf(i) sizeof(i)
#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define rep(i, L, R) for(ll i = L;i<=R;i++)
#define pcis precision
#define sz(a) ((ll) a.size())

template<typename T>
struct infinity {
	static constexpr T max=std::numeric_limits<T>::max();
	static constexpr T min=std::numeric_limits<T>::min();
	static constexpr T value=std::numeric_limits<T>::max()/2;
	static constexpr T mvalue=std::numeric_limits<T>::min()/2;
};
template<typename T>constexpr T INF=infinity<T>::value;
constexpr ll lINF=INF<ll>;
constexpr int iINF = INF<int>;
constexpr ld PI = 3.1415926535897932384626;

vvi A;

// 전체를 채워도 가능하면 => 전체를 채움

bool check(ll N, ll M, ll K) {
	if (N*M < K*4) {
		return false;
	}
	if (N%2 == 1 || M%2 == 1) {
		return false;
	}

	if (N*M/4 - 1 == K) {
		return false;
	}

	if (K < max(N, M)/2 || N*M/4 < K) {
		return false;
	}
	return true;
}

bool construct(ll lx , ll rx, ll ly, ll ry, ll K) {
	ll dx = rx - lx + 1;
	ll dy = ry - ly + 1;
	ll N = dx;
	ll M = dy;

	if (!check(N, M, K)) return false;

//	cout << "con " << N << " " << M << " " << K << endl;

	if (M==2) {
		if (N/2 != K) return false;
		for (ll i = lx; i+1<=rx; i+= 2) {
			A[i][ly] = ((i-lx)/2+1);
			A[i+1][ly] = ((i-lx)/2+1);
			A[i][ly+1] = ((i-lx)/2+1);
			A[i+1][ly+1] = ((i-lx)/2+1);
		}
		return true;
	}

	if ((N/2 - 1) <= K &&K <= (N/2 - 1)*(M/2 - 1)) {
		for (ll i = 1; i<=dx; i++) {
			ll x = lx + i-1;
			ll y = ly;
			A[x][y] = K;
		}

		for (ll i = 1; i<=dx; i++) {
			ll x = lx + i-1;
			ll y = ry;
			A[x][y] = K;
		}

		for (ll i = 1; i<=dy; i++) {
			ll x = lx;
			ll y = ly + i-1;
			A[x][y] = K;
		}

		for (ll i = 1; i<=dy; i++) {
			ll x = rx;
			ll y = ly + i-1;
			A[x][y] = K;
		}

		return construct(lx+1, rx-1, ly+1, ry-1, K-1);
	}

	// 적당히 몇개 묶어야함
	// 걍 naive하게 찾자

	ll MX = (N/2)*(M/2);

	if (K <= (N/2-2)*(M/2) + (M/2)) {
		// 대충 이 선에서 컷당함

		ll at = K - (N*M/4 - N/2 - M/2 + 2);

//		for (ll i = 1; i<=N/2; i++) {
//			// i*2개를 가져감
//			ll cnt = i*(M/2) + (N/2 - i - 1)*(M/2 - 1) + 1;// 개임 , 정확히는 N*M/4 -N/2 - M/2  + i  +  2를 뜻함
//		}

		// 1 ~ at*2까지는 그냥 채움
		// 나머지는 잘 채움
		ll id = 0;

		for (ll i = 1; i<=at*2; i+=2) {
			for (ll j = 1; j<=M; j+=2) {
				id++;
				ll x = lx + i-1;
				ll y = ly + j-1;
//				cout << x << " : " << y << " => " << id<<endl;
				A[x][y] = id;
				A[x+1][y] = id;
				A[x][y+1] = id;
				A[x+1][y+1] = id;
			}
		}

		for (ll i = at*2 + 2; i+1<=N; i+=2) {
			for (ll j = 2; j+1<=M-1; j+=2) {
				id++;
				ll x = lx + i-1;
				ll y = ly + j-1;

				A[x][y] = id;
				A[x+1][y] = id;
				A[x][y+1] = id;
				A[x+1][y+1] = id;
			}
		}

//		cout << "------------------------" << endl;
//
//		rep(i,1,N) {
//			rep(j,1,M) {
//				cout << A[i][j] << " ";
//			}
//			cout << endl;
//		}
//
//		cout << "------------------------" << endl;

		for (ll i = at*2+1; i<=N; i++) {
			ll x = lx + i-1;
			ll y = ly;
			A[x][y] = K;
		}

		for (ll i = at*2+1; i<=N; i++) {
			ll x = lx + i-1;
			ll y = ry;
			A[x][y] = K;
		}

		for (ll i = 1; i<=dy; i++) {
			ll x = lx + at*2;
			ll y = ly + i-1;
			A[x][y] = K;
		}

		for (ll i = 1; i<=dy; i++) {
			ll x = rx;
			ll y = ly + i-1;
			A[x][y] = K;
		}

		return true;
	} else {
		// 내부까지 들어가야함
		ll id = 0;

		for (ll i = 1; i<=N-4; i+=2) {
			for (ll j = 1; j<=M; j+=2) {
				id++;
				ll x = lx + i-1;
				ll y = ly + j-1;
				A[x][y] = K-id+1;
				A[x+1][y] = K-id+1;
				A[x][y+1] = K-id+1;
				A[x+1][y+1] = K-id+1;
			}
		}

		K -= id;
		// 1 ~ K까지 쓰면 됨

		lx += N-4;
		N = rx - lx + 1;// 갱신

		id = 0;

		if ((N/2)*(M/2) == K) {
			for (ll i = 1; i<=N; i+=2) {
				for (ll j = 1; j<=M; j+=2) {
					id++;
					ll x = lx + i-1;
					ll y = ly + j-1;
					A[x][y] = K-id+1;
					A[x+1][y] = K-id+1;
					A[x][y+1] = K-id+1;
					A[x+1][y+1] = K-id+1;
				}
			}
			return true;

		} else {
			// 적당히 묶다가 끝남

			// 위에서부터 i (<= M/2)개를 쓰는 경우

			//  i*2 + (M/2 - i - 1)*1 + 1 개이다
			// == i + M/2

			assert(N==4);

			ll at = K - M/2;
			// 앞에서 at개까지 먹음

			for (ll i = 1; i<=N; i+=2) {
				for (ll j = 1; j<=at*2; j+=2) {
					id++;
					ll x = lx + i-1;
					ll y = ly + j-1;
					A[x][y] = id;
					A[x+1][y] = id;
					A[x][y+1] = id;
					A[x+1][y+1] = id;
				}
			}

			for (ll i = 2; i+1<=N; i+=2) {
				for (ll j = at*2 + 2; j<=M; j+=2) {
					id++;
					ll x = lx + i-1;
					ll y = ly + j-1;
					A[x][y] = id;
					A[x+1][y] = id;
					A[x][y+1] = id;
					A[x+1][y+1] = id;
				}
			}

			for (ll i = at*2 + 1; i<=M; i++) {
				ll x = lx;
				ll y = ly + i-1;
				A[x][y] = K;
			}
			for (ll i = at*2 + 1; i<=M; i++) {
				ll x = rx;
				ll y = ly + i-1;
				A[x][y] = K;
			}
			
			
//			cout << lx << " " << rx << " :: "<< ly << " " << ry << endl;
			A[lx+1][ly+at*2] = K;
			A[lx+2][ly+at*2] = K;
			cout << M << endl;
			A[lx+1][(ly-1)+M] = K;
			A[lx+2][(ly-1)+M] = K;

			return true;
		}
	}

}

void _main() {

	ll T;
	cin >> T;
	while (T--) {

		ll N, M, K;
		cin >> N >> M >> K;

		if (N*M < K*4) {
			cout << "NO" << endl;
			continue;
		}
		if (N%2 == 1 || M%2 == 1) {
			cout << "NO" << endl;
			continue;
		}

		if (N*M/4 - 1 == K) {
			cout << "NO" << endl;
			continue;
		}

		if (K < max(N, M)/2 || N*M/4 < K) {
			cout << "NO" << endl;
			continue;
		}

		// 이러면 가능은 하다

		bool swp = (N < M);
		if (N<M) swap(N, M);// 거꾸로 해버림 일단

		A.clear();
		A.resize(N+1);
		rep(i,1,N) A[i].resize(M+1, 0);
		if (!construct(1, N, 1, M, K)) {
			cout << "NO" << endl;
			continue;
		}

		cout << "YES" << endl;

		if (swp) swap(N, M);
		rep(i,1,N) {
			rep(j,1,M) {
				cout << (swp?A[j][i]:A[i][j]) << " ";// 그리고 나중에 뒤집음
			}
			cout << endl;
		}

	}


}

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