Submission #1119029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119029		Vanio	Gardening (RMI21_gardening)	C++17	5 / 100	1060 ms	1104 KiB

Main

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("avx2")*/

#define ll int64_t

#include<bits/stdc++.h>
using namespace std;

const ll MAXN=2e5+3;
ll n,m,k,ans[7][MAXN],tindx;

bool rec(ll x, ll y, ll tn, ll tm, ll tk){
    if(tn%2==1 || tm%2==1 || tk*4>tn*tm) return 0;

    if(tk==0){
        if(tn==0 || tm==0) return 1;
        return 0;
    }

    if(tn%2==0 && tm%2==0 && tn*tm==tk*4){
        for(ll i=1;i<=n-1;i+=2){
            for(ll j=1;j<=m-1;j+=2){
                ans[i+x-1][j+y-1]=tindx;
                ans[i+x-1+1][j+y-1]=tindx;
                ans[i+x-1][j+y-1+1]=tindx;
                ans[i+x-1+1][j+y-1+1]=tindx;
                tindx++;
            }
        }
        return 1;
    }

    for(ll ik=1;ik<tk;ik++){
        if((rec(x,y+2,tn,tm-2,ik)==1 && rec(x+2,y,tn-2,2,tk-ik-1)==1) || (rec(x+2,y,tn-2,tm,ik)==1 && rec(x,y+2,2,tm-2,tk-ik-1)==1)){
            ans[x][y]=tindx;
            ans[x+1][y]=tindx;
            ans[x][y+1]=tindx;
            ans[x+1][y+1]=tindx;
            tindx++;
            return 1;
        }
    }

    for(ll i=4;i<=tn;i+=2){
        for(ll j=4;j<=tm;j+=2){
            for(ll ik1=1;ik1<tk;ik1++){
                if(rec(x+1,y+1,i-2,j-2,ik1)==0) continue;
                for(ll ik2=ik1;ik2<tk;ik2++){
                    if((rec(x,y+j,tn,tm-j,ik2-ik1)==1 && rec(x+i,y,tn-i,j,tk-ik2-1)==1) || (rec(x+i,y,tn-i,tm,ik2-ik1)==1 && rec(x,y+j,i,tm-j,tk-ik2-1)==1)){
                        for(ll t=1;t<=i;t++){
                            ans[t+x-1][y]=tindx;
                            ans[t+x-1][y+j-1]=tindx;
                        }
                        for(ll t=1;t<=j;t++){
                            ans[x][t+y-1]=tindx;
                            ans[x+i-1][t+y-1]=tindx;
                        }
                        tindx++;
                        return 1;
                    }
                }
            }
        }
    }

    return 0;
}

void solve(){
    cin>>n>>m>>k;

    tindx=1;
    if(rec(1,1,n,m,k)==0) cout<<"NO\n";
    else{
        cout<<"YES\n";

        set<ll> s;
        ll rv[n*m];
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++) s.insert(ans[i][j]);
        }
        ll i=1;
        for(auto it : s){
            rv[it]=i;
            i++;
        }

        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=m;j++) cout<<rv[ans[i][j]]<<" ";
            cout<<'\n';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    ll t=1;
    cin>>t;
    while(t--) solve();

    return 0;
}
/*
4
2 2 2
2 2 1
4 4 4
4 4 2
*/

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