oj.uz

Submission #498644

# Submission time Handle Problem Language Result Execution time Memory
498644 2021-12-26T04:42:15 Z model_code Gardening (RMI21_gardening) C++17
100 / 100
 54 ms 924 KB 
// gardening_100_tamio.cpp
#include <bits/stdc++.h>
using namespace std;

// 38 6 36

template <typename T>
void build(int n, int m, int k, T it) {
    auto print_rect = [&](int i0, int i1, int j0, int j1) {
        for (int i = i0; i <= i1; ++i) it[i][j0] = it[i][j1] = k;
        for (int j = j0; j <= j1; ++j) it[i0][j] = it[i1][j] = k;
        --k;
    };

    auto do_all_sq = [&]() {
        for (int i = 0; i < n; ++i)
            for (int j = 0
            ; j < m; ++j)
                if (it[i][j] == 0) print_rect(i, i + 1, j, j + 1);
    };

    int critical = ((n - 2) / 2) * ((m - 2) / 2) + 1;

    if (k == (n / 2) * m / 2)
        do_all_sq();
    else if (k > critical) {
        int diff = k - critical, diff_i = min(diff, (n - 4) / 2),
            diff_j = diff - diff_i;

        print_rect(0, n - 2 * diff_i - 1, 0, m - 2 * diff_j - 1);
        do_all_sq();
    } else if (k == critical - 1) {
        if (n < m) {
            print_rect(0, n - 1, 0, m - 3);
            print_rect(1, 4, 1, 4);
            do_all_sq();
        } else {
            print_rect(0, n - 3, 0, m - 1);
            print_rect(1, 4, 1, 4);
            do_all_sq();
        }
    } else {
        print_rect(0, n - 1, 0, m - 1);

        for (int i = 0; i < n; ++i) ++it[i];

        build(n - 2, m - 2, k, it + 1);
    }
}

#ifdef TESTING

#define DEF_ENV(name) int env_##name = atoi(getenv(#name))

#endif

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

    int t;
    cin >> t;

#ifdef TESTING
    long long s = 0;

    DEF_ENV(N);
    DEF_ENV(M);
    DEF_ENV(eq);
#endif

    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;

#ifdef TESTING
        assert(1 <= n && n <= 200000);
        assert(1 <= m && m <= 200000);
        assert(1 <= k && k <= (long long)n * m);

        assert(1 <= n && n <= env_N);
        assert(1 <= m && m <= env_M);
        assert(!env_eq || n == m);
#endif
        if (n % 2 == 1 || m % 2 == 1 || k < max(n / 2, m / 2) ||
            k > (n / 2) * (m / 2) || k == (n / 2) * (m / 2) - 1 ||
            (n == m && k == n / 2 + 1))
            cout << "NO\n";
        else {
            cout << "YES\n";
#ifdef TESTING
            s += (long long)n * m;
            assert(s <= 200000);
#endif
            vector<vector<int>> buf(n, vector<int>(m, 0));

            vector<vector<int>::iterator> its;

            transform(begin(buf), end(buf), back_inserter(its),
                      [](vector<int>& v) { return begin(v); });

            build(n, m, k, begin(its));

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) cout << buf[i][j] << ' ';
                cout << '\n';
            }
            cout << flush;
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 708 KB Correct! Azusa and Laika like the garden :)
2 Correct 13 ms 536 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 696 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 708 KB Correct! Azusa and Laika like the garden :)
2 Correct 13 ms 536 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 696 KB Correct! Azusa and Laika like the garden :)
4 Correct 13 ms 568 KB Correct! Azusa and Laika like the garden :)
5 Correct 13 ms 588 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 716 KB Correct! Azusa and Laika like the garden :)
2 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
3 Correct 8 ms 588 KB Correct! Azusa and Laika like the garden :)
4 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
5 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
6 Correct 9 ms 648 KB Correct! Azusa and Laika like the garden :)
7 Correct 10 ms 620 KB Correct! Azusa and Laika like the garden :)
8 Correct 9 ms 668 KB Correct! Azusa and Laika like the garden :)
9 Correct 10 ms 600 KB Correct! Azusa and Laika like the garden :)
10 Correct 9 ms 612 KB Correct! Azusa and Laika like the garden :)
11 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
12 Correct 11 ms 692 KB Correct! Azusa and Laika like the garden :)
13 Correct 8 ms 668 KB Correct! Azusa and Laika like the garden :)

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
2 Correct 3 ms 440 KB Correct! Azusa and Laika like the garden :)
3 Correct 5 ms 436 KB Correct! Azusa and Laika like the garden :)
4 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
5 Correct 6 ms 460 KB Correct! Azusa and Laika like the garden :)
6 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
7 Correct 6 ms 436 KB Correct! Azusa and Laika like the garden :)
8 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
9 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
10 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
11 Correct 3 ms 416 KB Correct! Azusa and Laika like the garden :)
12 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
13 Correct 4 ms 452 KB Correct! Azusa and Laika like the garden :)
14 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
15 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
16 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
17 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 708 KB Correct! Azusa and Laika like the garden :)
2 Correct 13 ms 536 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 696 KB Correct! Azusa and Laika like the garden :)
4 Correct 13 ms 568 KB Correct! Azusa and Laika like the garden :)
5 Correct 13 ms 588 KB Correct! Azusa and Laika like the garden :)
6 Correct 11 ms 716 KB Correct! Azusa and Laika like the garden :)
7 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
8 Correct 8 ms 588 KB Correct! Azusa and Laika like the garden :)
9 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
10 Correct 9 ms 588 KB Correct! Azusa and Laika like the garden :)
11 Correct 9 ms 648 KB Correct! Azusa and Laika like the garden :)
12 Correct 10 ms 620 KB Correct! Azusa and Laika like the garden :)
13 Correct 9 ms 668 KB Correct! Azusa and Laika like the garden :)
14 Correct 10 ms 600 KB Correct! Azusa and Laika like the garden :)
15 Correct 9 ms 612 KB Correct! Azusa and Laika like the garden :)
16 Correct 9 ms 716 KB Correct! Azusa and Laika like the garden :)
17 Correct 11 ms 692 KB Correct! Azusa and Laika like the garden :)
18 Correct 8 ms 668 KB Correct! Azusa and Laika like the garden :)
19 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
20 Correct 3 ms 440 KB Correct! Azusa and Laika like the garden :)
21 Correct 5 ms 436 KB Correct! Azusa and Laika like the garden :)
22 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
23 Correct 6 ms 460 KB Correct! Azusa and Laika like the garden :)
24 Correct 3 ms 460 KB Correct! Azusa and Laika like the garden :)
25 Correct 6 ms 436 KB Correct! Azusa and Laika like the garden :)
26 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
27 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
28 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
29 Correct 3 ms 416 KB Correct! Azusa and Laika like the garden :)
30 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
31 Correct 4 ms 452 KB Correct! Azusa and Laika like the garden :)
32 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
33 Correct 5 ms 460 KB Correct! Azusa and Laika like the garden :)
34 Correct 4 ms 460 KB Correct! Azusa and Laika like the garden :)
35 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
36 Correct 13 ms 832 KB Correct! Azusa and Laika like the garden :)
37 Correct 13 ms 776 KB Correct! Azusa and Laika like the garden :)
38 Correct 12 ms 788 KB Correct! Azusa and Laika like the garden :)
39 Correct 14 ms 808 KB Correct! Azusa and Laika like the garden :)
40 Correct 13 ms 828 KB Correct! Azusa and Laika like the garden :)
41 Correct 15 ms 820 KB Correct! Azusa and Laika like the garden :)
42 Correct 13 ms 780 KB Correct! Azusa and Laika like the garden :)
43 Correct 14 ms 848 KB Correct! Azusa and Laika like the garden :)
44 Correct 13 ms 816 KB Correct! Azusa and Laika like the garden :)
45 Correct 12 ms 820 KB Correct! Azusa and Laika like the garden :)
46 Correct 13 ms 836 KB Correct! Azusa and Laika like the garden :)
47 Correct 14 ms 924 KB Correct! Azusa and Laika like the garden :)
48 Correct 13 ms 824 KB Correct! Azusa and Laika like the garden :)
49 Correct 14 ms 896 KB Correct! Azusa and Laika like the garden :)
50 Correct 17 ms 848 KB Correct! Azusa and Laika like the garden :)
51 Correct 12 ms 716 KB Correct! Azusa and Laika like the garden :)
52 Correct 13 ms 812 KB Correct! Azusa and Laika like the garden :)
53 Correct 14 ms 808 KB Correct! Azusa and Laika like the garden :)
54 Correct 12 ms 844 KB Correct! Azusa and Laika like the garden :)
55 Correct 13 ms 844 KB Correct! Azusa and Laika like the garden :)
56 Correct 13 ms 844 KB Correct! Azusa and Laika like the garden :)
57 Correct 12 ms 860 KB Correct! Azusa and Laika like the garden :)
58 Correct 14 ms 844 KB Correct! Azusa and Laika like the garden :)
59 Correct 13 ms 824 KB Correct! Azusa and Laika like the garden :)
60 Correct 14 ms 880 KB Correct! Azusa and Laika like the garden :)