oj.uz

Submission #743611

# Submission time Handle Problem Language Result Execution time Memory
743611 2023-05-17T14:35:32 Z hmm789 Gardening (RMI21_gardening) C++14
100 / 100
 22 ms 916 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
 
vector<vector<int>> a;
int clr = 1;
void solve(int l, int r, int u, int d, int k) {
    int n = d-u+1, m = r-l+1;
    if(n <= 0 || m <= 0) return;
    if(k == n*m/4) {
        for(int i = u; i <= d; i++) {
            for(int j = l; j <= r; j++) {
                if((i-u)%2==0) {
                    if((j-l)%2==0) a[i][j] = clr;
                    else a[i][j] = clr++;
                } else a[i][j] = a[i-1][j];
            }
        }
    } else if(k >= n*m/4-n/2-m/2+2) {
        int num = n*m/4-k;
        if(num*2 <= m) {
            for(int i = l; i < l+num*2; i++) a[u][i] = a[min(d, u+3)][i] = clr;
            for(int i = u; i <= min(d, u+3); i++) a[i][l] = a[i][l+num*2-1] = clr;
            clr++;
            solve(l+1, l+num*2-2, u+1, min(d, u+3)-1, num-1);
            solve(l+num*2, r, u, min(d, u+3), r-(l+num*2)+1);
            solve(l, r, min(d, u+3)+1, d, k-1-(num-1)-(r-(l+num*2)+1));
        } else {
            int cols = (num-m/2)*2+4;
            for(int i = l; i <= r; i++) a[u][i] = a[u+cols-1][i] = clr;
            for(int i = u; i < u+cols; i++) a[i][l] = a[i][r] = clr;
            clr++;
            solve(l+1, r-1, u+1, u+cols-2, (r-l-1)*(cols-2)/4);
            solve(l, r, u+cols, d, k-1-(r-l-1)*(cols-2)/4);
        }
    } else if(k == n*m/4-n/2-m/2+1) {
        if(m >= 8) {
            for(int i = l; i <= r-2; i++) a[u][i] = a[d][i] = clr;
            for(int i = u; i <= d; i++) a[i][l] = a[i][r-2] = clr;
            clr++;
            for(int i = l+1; i <= l+4; i++) a[u+1][i] = a[u+4][i] = clr;
            for(int i = u+1; i <= u+4; i++) a[i][l+1] = a[i][l+4] = clr;
            clr++;
            solve(l+2, l+3, u+2, u+3, 1);
            solve(l+1, l+4, u+5, d-1, (d-1-u-5+1));
            solve(l+5, r-3, u+1, d-1, (r-3-l-5+1)*(d-1-u-1+1)/4);
            solve(r-1, r, u, d, k-3-(d-1-u-5+1)-(r-3-l-5+1)*(d-1-u-1+1)/4);
        } else {
            for(int i = l; i <= r; i++) a[u][i] = a[d-2][i] = clr;
            for(int i = u; i <= d-2; i++) a[i][l] = a[i][r] = clr;
            clr++;
            for(int i = l+1; i <= l+4; i++) a[u+1][i] = a[u+4][i] = clr;
            for(int i = u+1; i <= u+4; i++) a[i][l+1] = a[i][l+4] = clr;
            clr++;
            solve(l+2, l+3, u+2, u+3, 1);
            solve(l+1, l+4, u+5, d-3, (d-3-u-5+1));
            solve(l, r, d-1, d, k-3-(d-3-u-5+1));
        }
    } else {
        for(int i = l; i <= r; i++) a[u][i] = a[d][i] = clr;
        for(int i = u; i <= d; i++) a[i][l] = a[i][r] = clr;
        clr++;
        solve(l+1, r-1, u+1, d-1, k-1);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int n, m, k;
        cin >> n >> m >> k;
        if(n % 2 == 1 || m % 2 == 1 || k > n*m/4 || k < max(n, m)/2 || k == n*m/4-1 || (n==m&&k==n/2+1)) {
            cout << "NO" << endl;
            continue;
        }
        a.clear();
        for(int i = 0; i < n; i++) {
            vector<int> v;
            for(int j = 0; j < m; j++) v.push_back(0);
            a.push_back(v);
        }
        clr = 1;
        solve(0, m-1, 0, n-1, k);
        cout << "YES" << endl;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 916 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 580 KB Correct! Azusa and Laika like the garden :)
3 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 916 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 580 KB Correct! Azusa and Laika like the garden :)
3 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
4 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
5 Correct 10 ms 680 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 664 KB Correct! Azusa and Laika like the garden :)
2 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
3 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
4 Correct 10 ms 668 KB Correct! Azusa and Laika like the garden :)
5 Correct 11 ms 548 KB Correct! Azusa and Laika like the garden :)
6 Correct 12 ms 596 KB Correct! Azusa and Laika like the garden :)
7 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
8 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
9 Correct 13 ms 580 KB Correct! Azusa and Laika like the garden :)
10 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
11 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
12 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
13 Correct 11 ms 596 KB Correct! Azusa and Laika like the garden :)

Subtask #5
39.0 / 39.0

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

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 916 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 580 KB Correct! Azusa and Laika like the garden :)
3 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
4 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
5 Correct 10 ms 680 KB Correct! Azusa and Laika like the garden :)
6 Correct 10 ms 664 KB Correct! Azusa and Laika like the garden :)
7 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
8 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
9 Correct 10 ms 668 KB Correct! Azusa and Laika like the garden :)
10 Correct 11 ms 548 KB Correct! Azusa and Laika like the garden :)
11 Correct 12 ms 596 KB Correct! Azusa and Laika like the garden :)
12 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
13 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
14 Correct 13 ms 580 KB Correct! Azusa and Laika like the garden :)
15 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
16 Correct 10 ms 596 KB Correct! Azusa and Laika like the garden :)
17 Correct 9 ms 596 KB Correct! Azusa and Laika like the garden :)
18 Correct 11 ms 596 KB Correct! Azusa and Laika like the garden :)
19 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
20 Correct 3 ms 468 KB Correct! Azusa and Laika like the garden :)
21 Correct 3 ms 468 KB Correct! Azusa and Laika like the garden :)
22 Correct 7 ms 468 KB Correct! Azusa and Laika like the garden :)
23 Correct 5 ms 468 KB Correct! Azusa and Laika like the garden :)
24 Correct 3 ms 448 KB Correct! Azusa and Laika like the garden :)
25 Correct 3 ms 468 KB Correct! Azusa and Laika like the garden :)
26 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
27 Correct 4 ms 448 KB Correct! Azusa and Laika like the garden :)
28 Correct 5 ms 468 KB Correct! Azusa and Laika like the garden :)
29 Correct 2 ms 340 KB Correct! Azusa and Laika like the garden :)
30 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
31 Correct 4 ms 572 KB Correct! Azusa and Laika like the garden :)
32 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
33 Correct 4 ms 468 KB Correct! Azusa and Laika like the garden :)
34 Correct 5 ms 484 KB Correct! Azusa and Laika like the garden :)
35 Correct 5 ms 468 KB Correct! Azusa and Laika like the garden :)
36 Correct 14 ms 784 KB Correct! Azusa and Laika like the garden :)
37 Correct 12 ms 852 KB Correct! Azusa and Laika like the garden :)
38 Correct 12 ms 740 KB Correct! Azusa and Laika like the garden :)
39 Correct 13 ms 864 KB Correct! Azusa and Laika like the garden :)
40 Correct 12 ms 764 KB Correct! Azusa and Laika like the garden :)
41 Correct 13 ms 852 KB Correct! Azusa and Laika like the garden :)
42 Correct 12 ms 832 KB Correct! Azusa and Laika like the garden :)
43 Correct 15 ms 784 KB Correct! Azusa and Laika like the garden :)
44 Correct 13 ms 852 KB Correct! Azusa and Laika like the garden :)
45 Correct 12 ms 772 KB Correct! Azusa and Laika like the garden :)
46 Correct 12 ms 852 KB Correct! Azusa and Laika like the garden :)
47 Correct 14 ms 852 KB Correct! Azusa and Laika like the garden :)
48 Correct 13 ms 788 KB Correct! Azusa and Laika like the garden :)
49 Correct 13 ms 812 KB Correct! Azusa and Laika like the garden :)
50 Correct 16 ms 832 KB Correct! Azusa and Laika like the garden :)
51 Correct 12 ms 724 KB Correct! Azusa and Laika like the garden :)
52 Correct 12 ms 740 KB Correct! Azusa and Laika like the garden :)
53 Correct 13 ms 868 KB Correct! Azusa and Laika like the garden :)
54 Correct 14 ms 808 KB Correct! Azusa and Laika like the garden :)
55 Correct 12 ms 760 KB Correct! Azusa and Laika like the garden :)
56 Correct 14 ms 844 KB Correct! Azusa and Laika like the garden :)
57 Correct 13 ms 808 KB Correct! Azusa and Laika like the garden :)
58 Correct 13 ms 852 KB Correct! Azusa and Laika like the garden :)
59 Correct 14 ms 876 KB Correct! Azusa and Laika like the garden :)
60 Correct 14 ms 808 KB Correct! Azusa and Laika like the garden :)