Submission #1340523

#TimeUsernameProblemLanguageResultExecution timeMemory
1340523NHristovGardening (RMI21_gardening)C++20
100 / 100
12 ms980 KiB
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'

using namespace std;

const int N=2e5+5;

vector<vector<int>> ans;

bool chk(int n, int m, int k) {
    if(n%2==1||m%2==1)
        return 0;
    if(n==m&&k==n/2+1)
        return 0;
    if(k==n*m/4-1)
        return 0;
    if(!(max(n, m)/2<=k&&k<=n*m/4))
        return 0;
    return 1;
}
bool slv(int n, int m, int k, int x, int y, int c) {
    if(!chk(n, m, k))
        return 0;
    if(k==n*m/4) {
        for(int i=0; i<n; i+=2) {
            for(int q=0; q<m; q+=2) {
                c++;
                ans[x+i][y+q]=c;
                ans[x+i][y+q+1]=c;
                ans[x+i+1][y+q]=c;
                ans[x+i+1][y+q+1]=c;
            }
        }
        return 1;
    }
    if(n==2||m==2)
        return 0;
    if(chk(n-2, m-2, k-1)) {
        if(slv(n-2, m-2, k-1, x+1, y+1, c)) {
            for(int i=0; i<n; i++) {
                ans[x+i][y]=c+k;
                ans[x+i][y+(m-1)]=c+k;
            }
            for(int i=0; i<m; i++) {
                ans[x][y+i]=c+k;
                ans[x+(n-1)][y+i]=c+k;
            }
            return 1;
        }
    }
    for(int i=2; 2*i<=n; i+=2) {
        int l=max(max(i, m)/2, k-(n-i)*m/4), r=min(i*m/4, k-max(n-i, m)/2);
        for(int nwk=l; nwk<=r; nwk++) {
            if(slv(i, m, nwk, x, y, c)&&slv(n-i, m, k-nwk, x+i, y, c+nwk))
                return 1;
        }
    }
    for(int i=2; 2*i<=m; i+=2) {
        int l=max(max(n, i)/2, k-(m-i)*n/4), r=min(i*n/4, k-max(m-i, n)/2);
        for(int nwk=l; nwk<=r; nwk++) {
            if(slv(n, i, nwk, x, y, c)&&slv(n, m-i, k-nwk, x, y+i, c+nwk))
                return 1;
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    ll tot=0;
    while(t--) {
        int n, m, k;
        cin >> n >> m >> k;
        tot+=(ll)(n*m);
        if(tot>200000) {
            cout << "NO" << endl;
            continue;
        }
        if(!chk(n, m, k)) {
            cout << "NO" << endl;
            continue;
        }
        ans=vector<vector<int>> (n, vector<int>(m));
        slv(n, m, k, 0, 0, 0);
        cout << "YES" << endl;
        for(int i=0; i<n; i++) {
            for(int q=0; q<m; q++)
                cout << ans[i][q] << " ";
            cout << endl;
        }
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...