Submission #743668

#	Time	Username	Problem	Language	Result	Execution time	Memory
743668		beepbeepsheep	Gardening (RMI21_gardening)	C++17	100 / 100	21 ms	836 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
#define ll long long
#define ii pair<ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=1e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll cnt=1;
void solve(ll n1, ll n2, ll m1, ll m2, vector<vector<ll>> &v, ll k=-1){
	cerr<<k<<'x'<<endl;
	ll n=(n2-n1+1),m=(m2-m1+1);
	if (k==-1 || n*m==4*k){
		cerr<<1<<endl;
		for (int i=n1;i<=n2;i+=2){
			for (int j=m1;j<=m2;j+=2){
				v[i][j]=cnt;
				v[i+1][j]=cnt;
				v[i][j+1]=cnt;
				v[i+1][j+1]=cnt;
				cnt++;
			}
		}
	}
	else if (k<(n*m)/4-n/2-m/2+1){ //fill border //6
		cerr<<2<<endl;
		for (int i=m1;i<=m2;i++){
			v[n1][i]=cnt;
			v[n2][i]=cnt;
		}
		for (int i=n1;i<=n2;i++){
			v[i][m1]=cnt;
			v[i][m2]=cnt;
		}
		cnt++;
		solve(n1+1,n2-1,m1+1,m2-1,v,k-1);
	}
	else if (k==(n*m)/4-n/2-m/2+1){
		cerr<<3<<endl;
		for (int i=m1;i<=m2-2;i++){
			v[n1][i]=cnt;
			v[n2][i]=cnt;
		}
		for (int i=n1;i<=n2;i++){
			v[i][m1]=cnt;
			v[i][m2-2]=cnt;
		}
		cnt++;
		solve(n1,n2,m2-1,m2,v);
		solve(n1+1,n2-1,m1+1,m2-3,v,k-n/2-1);
	}
	else{
		cerr<<4<<endl;
		ll diff=n*m/4-k;
		ll y=2;
		ll x=diff+2-y;
		if (x>n/2){
			y+=x-n/2;
			x=n/2;
		}
		x*=2,y*=2;
		for (int i=n1;i<n1+x;i++){
			v[i][m1]=cnt;
			v[i][m1+y-1]=cnt;
		}
		for (int i=m1;i<m1+y;i++){
			v[n1][i]=cnt;
			v[n1+x-1][i]=cnt;
		}
		cnt++;
		solve(n1+1,n1+x-2,m1+1,m1+y-2,v);
		if (n1+x!=n2) solve(n1+x,n2,m1,m1+y-1,v);
		if (m1+y!=m2) solve(n1,n2,m1+y,m2,v);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc,n,m,k;
	cin>>tc;
	while (tc--){
		cin>>n>>m>>k;
		cnt=1;
		if (n&1 or m&1){
			cout<<"NO"<<endl;
			continue;
		}
		if (n==m && k==n/2+1){
			cout<<"NO"<<endl;
			continue;
		}
		if (k==n*m/4-1){
			cout<<"NO"<<endl;
			continue;
		}
		if (k<max(n,m)/2){
			cout<<"NO"<<endl;
			continue;
		}
		if (k>n*m/4){
			cout<<"NO"<<endl;
			continue;
		}
		bool swapped=false;
		if (m<n) swap(n,m),swapped=true;
		vector<vector<ll>> v;
		for (int i=0;i<n;i++){
			v.emplace_back(vector<ll>());
			for (int j=0;j<m;j++){
				v[i].emplace_back(0);
			}
		}
		solve(0,n-1,0,m-1,v,k);
		cout<<"YES"<<endl;
		if (swapped){
			for (int i=0;i<m;i++){
				for (int j=0;j<n;j++){
					cout<<v[j][i]<<' ';
				}
				cout<<endl;
			}
			continue;
		}
		for (int i=0;i<n;i++){
			for (int j=0;j<m;j++){
				cout<<v[i][j]<<' ';
			}
			cout<<endl;
		}
		cerr<<endl;
	}
	return 0;
}

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