Submission #498643

#	Time	Username	Problem	Language	Result	Execution time	Memory
498643		model_code	Gardening (RMI21_gardening)	C++17	23 / 100	73 ms	820 KiB

Main

// gardening_100_panaete.cpp
#include <bits/stdc++.h>

using namespace std;
/// pasul 1: se determina numarul de benzi

int minColors(int N,int M,int b)
{
    return b+(N-2*b)*(M-2*b)/4;
}
int maxColors(int N,int M,int b)
{
    /// ocup un patrat de latura (2b+2) cu cele b benzi si un patrat central
    return N*M/4-b*(b+1);
}
void solveTest()
{
    int N,M,k;
    cin>>N>>M>>k;
    if(N%2){cout<<"NO\n";return;}
    if(M%2){cout<<"NO\n";return;}

    int blo=min(N/2,M/2);
    int bhi=0;
    if(k<minColors(N,M,blo)){cout<<"NO\n";return;}
    if(k>maxColors(N,M,bhi)){cout<<"NO\n";return;}
    int b=-1,bmi,colMin,colMax;
    while(b==-1&&blo>=bhi)
    {
        bmi=(blo+bhi)/2;
        //cout<<"Benzi: "<<bmi;
        colMax=maxColors(N,M,bmi);
        colMin=minColors(N,M,bmi);
        //cout<<" -> culori : [ "<<colMin<<" , "<<colMax<<" ]\n";
        if(k<colMin)bhi=bmi+1;
        else if(k>colMax) blo=bmi-1;
        else b=bmi;
    }
    if(b==-1){cout<<"NO\n";return;}
    cout<<"YES\n";
    /// matrice NxM
    vector<vector<int>> A(N,vector<int>(M,0));
    int ST=0,DR=2*b+1;
    int scad=maxColors(N,M,b)-k;
    int stepCol=M/2-b-1;
    int stepLin=N/2-b-1;
    for(int i=1;i<=b;i++)
    {
        int L,R,U,D;
        L=U=ST;
        R=D=DR;
        int scadCol=min(scad,stepCol);
        R+=2*scadCol;
        scad-=scadCol;
        int scadLin=min(scad,stepLin);
        D+=2*scadLin;
        scad-=scadLin;

        for(int col=L;col<=R;col++)
            A[U][col]=A[D][col]=i;
        for(int lin=U+1;lin<D;lin++)
            A[lin][L]=A[lin][R]=i;
        ST++;DR--;
    }
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<M;j++)
        {
            if(!A[i][j])
            {
                b++;
                A[i][j]=A[i][j+1]=A[i+1][j]=A[i+1][j+1]=b;
            }
            cout<<A[i][j]<<' ';
        }
        cout<<'\n';
    }
}
int main()
{
    int t;
    cin>>t;
    for(;t;t--)
        solveTest();
    return 0;
}

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