oj.uz

Submission #743668

# Submission time Handle Problem Language Result Execution time Memory
743668 2023-05-17T16:30:14 Z beepbeepsheep Gardening (RMI21_gardening) C++17
100 / 100
 21 ms 836 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 660 KB Correct! Azusa and Laika like the garden :)

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 660 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 524 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 620 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 660 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 524 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 620 KB Correct! Azusa and Laika like the garden :)
4 Correct 14 ms 572 KB Correct! Azusa and Laika like the garden :)
5 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 596 KB Correct! Azusa and Laika like the garden :)
2 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
3 Correct 9 ms 580 KB Correct! Azusa and Laika like the garden :)
4 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
5 Correct 14 ms 612 KB Correct! Azusa and Laika like the garden :)
6 Correct 9 ms 568 KB Correct! Azusa and Laika like the garden :)
7 Correct 9 ms 580 KB Correct! Azusa and Laika like the garden :)
8 Correct 8 ms 580 KB Correct! Azusa and Laika like the garden :)
9 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
10 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
11 Correct 11 ms 572 KB Correct! Azusa and Laika like the garden :)
12 Correct 8 ms 596 KB Correct! Azusa and Laika like the garden :)
13 Correct 8 ms 596 KB Correct! Azusa and Laika like the garden :)

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Correct! Azusa and Laika like the garden :)
2 Correct 4 ms 340 KB Correct! Azusa and Laika like the garden :)
3 Correct 3 ms 340 KB Correct! Azusa and Laika like the garden :)
4 Correct 5 ms 468 KB Correct! Azusa and Laika like the garden :)
5 Correct 7 ms 468 KB Correct! Azusa and Laika like the garden :)
6 Correct 4 ms 456 KB Correct! Azusa and Laika like the garden :)
7 Correct 4 ms 456 KB Correct! Azusa and Laika like the garden :)
8 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
9 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
10 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
11 Correct 3 ms 340 KB Correct! Azusa and Laika like the garden :)
12 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
13 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
14 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
15 Correct 4 ms 452 KB Correct! Azusa and Laika like the garden :)
16 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
17 Correct 6 ms 468 KB Correct! Azusa and Laika like the garden :)

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 660 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 524 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 620 KB Correct! Azusa and Laika like the garden :)
4 Correct 14 ms 572 KB Correct! Azusa and Laika like the garden :)
5 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
6 Correct 11 ms 596 KB Correct! Azusa and Laika like the garden :)
7 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
8 Correct 9 ms 580 KB Correct! Azusa and Laika like the garden :)
9 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
10 Correct 14 ms 612 KB Correct! Azusa and Laika like the garden :)
11 Correct 9 ms 568 KB Correct! Azusa and Laika like the garden :)
12 Correct 9 ms 580 KB Correct! Azusa and Laika like the garden :)
13 Correct 8 ms 580 KB Correct! Azusa and Laika like the garden :)
14 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
15 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
16 Correct 11 ms 572 KB Correct! Azusa and Laika like the garden :)
17 Correct 8 ms 596 KB Correct! Azusa and Laika like the garden :)
18 Correct 8 ms 596 KB Correct! Azusa and Laika like the garden :)
19 Correct 3 ms 340 KB Correct! Azusa and Laika like the garden :)
20 Correct 4 ms 340 KB Correct! Azusa and Laika like the garden :)
21 Correct 3 ms 340 KB Correct! Azusa and Laika like the garden :)
22 Correct 5 ms 468 KB Correct! Azusa and Laika like the garden :)
23 Correct 7 ms 468 KB Correct! Azusa and Laika like the garden :)
24 Correct 4 ms 456 KB Correct! Azusa and Laika like the garden :)
25 Correct 4 ms 456 KB Correct! Azusa and Laika like the garden :)
26 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
27 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
28 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
29 Correct 3 ms 340 KB Correct! Azusa and Laika like the garden :)
30 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
31 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
32 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
33 Correct 4 ms 452 KB Correct! Azusa and Laika like the garden :)
34 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
35 Correct 6 ms 468 KB Correct! Azusa and Laika like the garden :)
36 Correct 13 ms 704 KB Correct! Azusa and Laika like the garden :)
37 Correct 15 ms 764 KB Correct! Azusa and Laika like the garden :)
38 Correct 16 ms 756 KB Correct! Azusa and Laika like the garden :)
39 Correct 14 ms 756 KB Correct! Azusa and Laika like the garden :)
40 Correct 13 ms 708 KB Correct! Azusa and Laika like the garden :)
41 Correct 12 ms 776 KB Correct! Azusa and Laika like the garden :)
42 Correct 12 ms 804 KB Correct! Azusa and Laika like the garden :)
43 Correct 14 ms 748 KB Correct! Azusa and Laika like the garden :)
44 Correct 14 ms 728 KB Correct! Azusa and Laika like the garden :)
45 Correct 12 ms 724 KB Correct! Azusa and Laika like the garden :)
46 Correct 12 ms 728 KB Correct! Azusa and Laika like the garden :)
47 Correct 13 ms 756 KB Correct! Azusa and Laika like the garden :)
48 Correct 13 ms 708 KB Correct! Azusa and Laika like the garden :)
49 Correct 12 ms 724 KB Correct! Azusa and Laika like the garden :)
50 Correct 14 ms 804 KB Correct! Azusa and Laika like the garden :)
51 Correct 11 ms 700 KB Correct! Azusa and Laika like the garden :)
52 Correct 12 ms 724 KB Correct! Azusa and Laika like the garden :)
53 Correct 13 ms 724 KB Correct! Azusa and Laika like the garden :)
54 Correct 18 ms 724 KB Correct! Azusa and Laika like the garden :)
55 Correct 13 ms 724 KB Correct! Azusa and Laika like the garden :)
56 Correct 13 ms 716 KB Correct! Azusa and Laika like the garden :)
57 Correct 15 ms 836 KB Correct! Azusa and Laika like the garden :)
58 Correct 12 ms 724 KB Correct! Azusa and Laika like the garden :)
59 Correct 14 ms 716 KB Correct! Azusa and Laika like the garden :)
60 Correct 14 ms 724 KB Correct! Azusa and Laika like the garden :)