oj.uz

Submission #632566

# Submission time Handle Problem Language Result Execution time Memory
632566 2022-08-20T10:47:51 Z boris_mihov Gardening (RMI21_gardening) C++17
5 / 100
 26 ms 5460 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

int n, m, k;
int sx, sy, ex, ey, curr;
std::vector <int> t[MAXN];
void putFrame()
{
    for (int i = sx ; i <= ex ; ++i)
    {
        t[i][sy] = curr;
        t[i][ey] = curr;
    }

    for (int i = sy ; i <= ey ; ++i)
    {
        t[sx][i] = curr;
        t[ex][i] = curr;
    }

    sx++;
    sy++;
    ex--;
    ey--;
    curr++;
}

void putRow()
{
    for (int i = 0 ; i < (ey - sy + 1) / 2 ; ++i)
    {
        t[sx][sy + 2*i] = curr;
        t[sx][sy + 2*i + 1] = curr;
        t[sx + 1][sy + 2*i] = curr;
        t[sx + 1][sy + 2*i + 1] = curr;
        curr++;
    }

    sx += 2;
}

void putCol()
{
    for (int i = 0 ; i < (ex - sx + 1) / 2 ; ++i)
    {
        t[sx + 2*i][sy] = curr;
        t[sx + 2*i + 1][sy] = curr;
        t[sx + 2*i][sy + 1] = curr;
        t[sx + 2*i + 1][sy + 1] = curr;
        curr++;
    }

    sy += 2;
}

void solve()
{
    if (n&1 || m&1)
    {
        std::cout << "NO\n";
        return;
    }

    if (k < std::min(n/2, m/2) || n*m/4 < k)
    {
        std::cout << "NO\n";
        return;
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        t[i].clear();
        t[i].resize(m + 1);
    }

    int realN = n;
    int realM = m;
    int realK = k;
    sx = 1;
    sy = 1;
    ex = n;
    ey = m;
    curr = 1;
    bool success = true;

    while (k >= 1)
    {
        if (n >= m && k - (ey - sy + 1) / 2 >= std::min((n-2)/2, m/2)) 
        {
            int newK = k - (ey - sy + 1) / 2;
            putRow();
            n -= 2;
            k = newK;
            continue;
        }

        if (m > n && k - (ex - sx + 1) / 2 >= std::min(n/2, (m-2)/2)) 
        {
            int newK = k - (ex - sx + 1) / 2;
            putCol();
            m -= 2;
            k = newK;
            continue;
        }

        if (k - (ey - sy + 1) / 2 >= std::min((n-2)/2, m/2)) 
        {
            int newK = k - (ey - sy + 1) / 2;
            putRow();
            n -= 2;
            k = newK;
            continue;
        }

        if (k - (ex - sx + 1) / 2 >= std::min(n/2, (m-2)/2)) 
        {
            int newK = k - (ex - sx + 1) / 2;
            putCol();
            m -= 2;
            k = newK;
            continue;
        }
        
        success &= !(std::min(n, m) == 2 && n != m);
        putFrame();
        n -= 2;
        m -= 2;
        k--;
    }

    if (!success)
    {
        n = realN;
        m = realM;
        k = realK;
        sx = 1;
        sy = 1;
        ex = n;
        ey = m;
        curr = 1;
        
        if ((n-2)*(m-2)/4 < k-1 || n == 2 || m == 2)
        {
            std::cout << "NO\n";
            return;
        }

        putFrame();
        n -= 2;
        m -= 2;
        k--;

        while (k >= 1)
        {
            if (n >= m && k - (ey - sy + 1) / 2 >= std::min((n-2)/2, m/2)) 
            {
                int newK = k - (ey - sy + 1) / 2;
                putRow();
                n -= 2;
                k = newK;
                continue;
            }

            if (m > n && k - (ex - sx + 1) / 2 >= std::min(n/2, (m-2)/2)) 
            {
                int newK = k - (ex - sx + 1) / 2;
                putCol();
                m -= 2;
                k = newK;
                continue;
            }

            if (k - (ey - sy + 1) / 2 >= std::min((n-2)/2, m/2)) 
            {
                int newK = k - (ey - sy + 1) / 2;
                putRow();
                n -= 2;
                k = newK;
                continue;
            }

            if (k - (ex - sx + 1) / 2 >= std::min(n/2, (m-2)/2)) 
            {
                int newK = k - (ex - sx + 1) / 2;
                putCol();
                m -= 2;
                k = newK;
                continue;
            }
            
            if (n != m && std::min(n, m) == 2)
            {
                std::cout << "NO\n";
                return;
            }

            putFrame();
            n -= 2;
            m -= 2;
            k--;
        }
    }

    std::cout << "YES\n";
    for (int i = 1 ; i <= realN ; ++i)
    {
        for (int j = 1 ; j <= realM ; ++j)
        {
            std::cout << t[i][j] << ' ';
        }

        std::cout << '\n';
    }
}

void read()
{
    std::cin >> n >> m >> k;
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int tests;
int main()
{
    fastIO();
    std::cin >> tests;

    while (tests--)
    {
        read();
        solve();
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5460 KB Correct! Azusa and Laika like the garden :)
2 Failed 9 ms 5204 KB Incorrect output
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5460 KB Correct! Azusa and Laika like the garden :)
2 Failed 9 ms 5204 KB Incorrect output
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 39.0

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

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5460 KB Correct! Azusa and Laika like the garden :)
2 Failed 9 ms 5204 KB Incorrect output
3 Halted 0 ms 0 KB -