Submission #1234034

#TimeUsernameProblemLanguageResultExecution timeMemory
1234034HanksburgerGardening (RMI21_gardening)C++20
100 / 100
11 ms960 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> ans;
void draw(int xl, int xr, int yl, int yr, int val)
{
    for (int i=yl; i<=yr; i++)
        ans[xl][i]=ans[xr][i]=val;
    for (int i=xl; i<=xr; i++)
        ans[i][yl]=ans[i][yr]=val;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m, k;
        cin >> n >> m >> k;
        if (n&1 || m&1)
        {
            cout << "NO\n";
            continue;
        }
        n/=2, m/=2, k=n*m-k;
        int swapped=0;
        if (n>m)
        {
            swap(n, m);
            swapped=1;
        }
        if (n==m && !(k==0 || (2<=k && k<=(n-1)*n-2) || k==(n-1)*n))
        {
            cout << "NO\n";
            continue;
        }
        if (n<m && !(k==0 || (2<=k && k<=(n-1)*m)))
        {
            cout << "NO\n";
            continue;
        }
        ans=vector<vector<int>>(n*2, vector<int>(m*2, 0));
        int nn=n, mm=m, cnt=0;
        while (k && (k==nn+mm-2 || k>=nn+mm))
        {
            draw(cnt, cnt+nn*2-1, cnt, cnt+mm*2-1, cnt+1);
            k-=nn+mm-2;
            nn--, mm--, cnt++;
        }
        if (k==nn+mm-1)
        {
            draw(cnt, cnt+5, cnt, cnt+3, cnt+1);
            draw(cnt, cnt+nn*2-1, cnt+4, cnt+mm*2-1, cnt+2);
            cnt+=2;
        }
        else if (k)
        {
            draw(cnt, cnt+max(2LL, k-mm+2)*2-1, cnt, cnt+min(mm, k)*2-1, cnt+1);
            cnt++;
        }
        for (int i=0; i<n*2; i++)
            for (int j=0; j<m*2; j++)
                if (!ans[i][j])
                    ans[i][j]=ans[i][j+1]=ans[i+1][j]=ans[i+1][j+1]=++cnt;
        cout << "YES\n";
        for (int i=0; i<(swapped?m:n)*2; i++)
        {
            for (int j=0; j<(swapped?n:m)*2; j++)
                cout << (swapped?ans[j][i]:ans[i][j]) << ' ';
            cout << '\n';
        }
    }
}
#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...