oj.uz

Submission #498643

# Submission time Handle Problem Language Result Execution time Memory
498643 2021-12-26T04:42:04 Z model_code Gardening (RMI21_gardening) C++17
23 / 100
 73 ms 820 KB 
// 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.0 / 5.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 820 KB Correct! Azusa and Laika like the garden :)
2 Failed 22 ms 596 KB Incorrect output
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 820 KB Correct! Azusa and Laika like the garden :)
2 Failed 22 ms 596 KB Incorrect output
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 592 KB Correct! Azusa and Laika like the garden :)
2 Correct 14 ms 668 KB Correct! Azusa and Laika like the garden :)
3 Correct 11 ms 592 KB Correct! Azusa and Laika like the garden :)
4 Correct 11 ms 588 KB Correct! Azusa and Laika like the garden :)
5 Correct 10 ms 516 KB Correct! Azusa and Laika like the garden :)
6 Correct 10 ms 624 KB Correct! Azusa and Laika like the garden :)
7 Correct 13 ms 588 KB Correct! Azusa and Laika like the garden :)
8 Correct 12 ms 588 KB Correct! Azusa and Laika like the garden :)
9 Correct 11 ms 540 KB Correct! Azusa and Laika like the garden :)
10 Correct 11 ms 552 KB Correct! Azusa and Laika like the garden :)
11 Correct 12 ms 512 KB Correct! Azusa and Laika like the garden :)
12 Correct 11 ms 564 KB Correct! Azusa and Laika like the garden :)
13 Correct 10 ms 468 KB Correct! Azusa and Laika like the garden :)

Subtask #5
0 / 39.0

# Verdict Execution time Memory Grader output
1 Failed 5 ms 424 KB Incorrect output
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 820 KB Correct! Azusa and Laika like the garden :)
2 Failed 22 ms 596 KB Incorrect output
3 Halted 0 ms 0 KB -