oj.uz

Submission #685473

# Submission time Handle Problem Language Result Execution time Memory
685473 2023-01-24T12:15:05 Z QwertyPi Gardening (RMI21_gardening) C++14
100 / 100
 118 ms 868 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[200000];

bool valid(int N, int M, int K){
    if(N % 2 == 1 || M % 2 == 1 || K > N * M / 4 || K < max(N, M) / 2 || K == N * M / 4 - 1) return false;
    if(N == 2 || M == 2) {
        if(K == N * M / 4) return true;
        else return false;
    }
    return true;
}

void solve(){
    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) {
        cout << "NO" << endl;
        return;
    }
    if(N == 2){
        if(K != M / 2){
            cout << "NO" << endl;
        }else{
            cout << "YES" << endl;
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    cout << j / 2 + 1 << ' ';
                }
                cout << endl;
            }
        }
        return;
    }
    
    if(M == 2){
        if(K != N / 2){
            cout << "NO" << endl;
        }else{
            cout << "YES" << endl;
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    cout << i / 2 + 1 << ' ';
                }
                cout << endl;
            }
        }
        return;
    }
    
    int x1 = 0, x2 = N - 1, y1 = 0, y2 = M - 1;
    while(K > 0){
        // cout << x2 - x1 + 1 << ' ' << y2 - y1 + 1 << ' ' << K << endl;
        if(x2 - x1 + 1 >= 4 && y2 - y1 + 1 >= 4 && valid(x2 - x1 - 1, y2 - y1 - 1, K - 1)){
            for(int x = x1; x <= x2; x++){
                a[x * M + y1] = a[x * M + y2] = K;
            }
            for(int y = y1; y <= y2; y++){
                a[x1 * M + y] = a[x2 * M + y] = K;
            }
            K--; x1++; x2--; y1++; y2--;
        }else if(valid(x2 - x1 - 1, y2 - y1 + 1, K - (y2 - y1 + 1) / 2)){
            for(int y = y1; y <= y2; y++){
                a[x1 * M + y] = a[(x1 + 1) * M + y] = K - (y - y1) / 2;
            }
            K -= (y2 - y1 + 1) / 2; x1 += 2;
        }else if(valid(x2 - x1 + 1, y2 - y1 - 1, K - (x2 - x1 + 1) / 2)){
            for(int x = x1; x <= x2; x++){
                a[x * M + y1] = a[x * M + (y1 + 1)] = K - (x - x1) / 2;
            }
            K -= (x2 - x1 + 1) / 2; y1 += 2;
        }else if(x2 - x1 + 1 == 4 && y2 - y1 + 1 == 4){
            if(K == 4){
                for(int x = x1; x <= x2; x++){
                    for(int y = y1; y <= y2; y++){
                        a[x * M + y] = (x - x1) / 2 * 2 + (y - y1) / 2 + 1;
                    }
                }
                K -= 4;
            }else if(K == 2){
                for(int x = x1; x <= x2; x++){
                    for(int y = y1; y <= y2; y++){
                        a[x * M + y] = 1;
                    }
                }
                for(int x = x1 + 1; x <= x2 - 1; x++){
                    for(int y = y1 + 1; y <= y2 - 1; y++){
                        a[x * M + y] = 2;
                    }
                }
                K -= 2;
            }else{
                assert(1 == 0);
            }
        }else if(x2 - x1 + 1 == 2){
            assert(K == (y2 - y1 + 1) / 2);
            for(int y = y1; y <= y2; y++){
                a[x1 * M + y] = (y - y1) / 2 + 1;
                a[(x1 + 1) * M + y] = (y - y1) / 2 + 1;
            }
            K -= (y2 - y1 + 1);
        }else if(y2 - y1 + 1 == 2){
            assert(K == (x2 - x1 + 1) / 2);
            for(int x = x1; x <= x2; x++){
                a[x * M + y1] = (x - x1) / 2 + 1;
                a[x * M + y1 + 1] = (x - x1) / 2 + 1;
            }
            K -= (x2 - x1 + 1);
        }else{
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            cout << a[i * M + j] << ' ';
        }
        cout << endl;
    }
}

int32_t main(){
    int T; cin >> T;
    while(T--){
        solve();
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 840 KB Correct! Azusa and Laika like the garden :)
2 Correct 23 ms 604 KB Correct! Azusa and Laika like the garden :)
3 Correct 22 ms 508 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 840 KB Correct! Azusa and Laika like the garden :)
2 Correct 23 ms 604 KB Correct! Azusa and Laika like the garden :)
3 Correct 22 ms 508 KB Correct! Azusa and Laika like the garden :)
4 Correct 25 ms 580 KB Correct! Azusa and Laika like the garden :)
5 Correct 22 ms 644 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 668 KB Correct! Azusa and Laika like the garden :)
2 Correct 14 ms 596 KB Correct! Azusa and Laika like the garden :)
3 Correct 13 ms 596 KB Correct! Azusa and Laika like the garden :)
4 Correct 17 ms 688 KB Correct! Azusa and Laika like the garden :)
5 Correct 14 ms 584 KB Correct! Azusa and Laika like the garden :)
6 Correct 14 ms 564 KB Correct! Azusa and Laika like the garden :)
7 Correct 15 ms 700 KB Correct! Azusa and Laika like the garden :)
8 Correct 14 ms 580 KB Correct! Azusa and Laika like the garden :)
9 Correct 15 ms 656 KB Correct! Azusa and Laika like the garden :)
10 Correct 15 ms 596 KB Correct! Azusa and Laika like the garden :)
11 Correct 13 ms 648 KB Correct! Azusa and Laika like the garden :)
12 Correct 17 ms 576 KB Correct! Azusa and Laika like the garden :)
13 Correct 17 ms 668 KB Correct! Azusa and Laika like the garden :)

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
2 Correct 5 ms 340 KB Correct! Azusa and Laika like the garden :)
3 Correct 5 ms 436 KB Correct! Azusa and Laika like the garden :)
4 Correct 8 ms 432 KB Correct! Azusa and Laika like the garden :)
5 Correct 8 ms 476 KB Correct! Azusa and Laika like the garden :)
6 Correct 5 ms 340 KB Correct! Azusa and Laika like the garden :)
7 Correct 6 ms 344 KB Correct! Azusa and Laika like the garden :)
8 Correct 7 ms 468 KB Correct! Azusa and Laika like the garden :)
9 Correct 6 ms 468 KB Correct! Azusa and Laika like the garden :)
10 Correct 6 ms 368 KB Correct! Azusa and Laika like the garden :)
11 Correct 5 ms 308 KB Correct! Azusa and Laika like the garden :)
12 Correct 7 ms 436 KB Correct! Azusa and Laika like the garden :)
13 Correct 6 ms 468 KB Correct! Azusa and Laika like the garden :)
14 Correct 8 ms 388 KB Correct! Azusa and Laika like the garden :)
15 Correct 5 ms 340 KB Correct! Azusa and Laika like the garden :)
16 Correct 8 ms 468 KB Correct! Azusa and Laika like the garden :)
17 Correct 6 ms 380 KB Correct! Azusa and Laika like the garden :)

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 840 KB Correct! Azusa and Laika like the garden :)
2 Correct 23 ms 604 KB Correct! Azusa and Laika like the garden :)
3 Correct 22 ms 508 KB Correct! Azusa and Laika like the garden :)
4 Correct 25 ms 580 KB Correct! Azusa and Laika like the garden :)
5 Correct 22 ms 644 KB Correct! Azusa and Laika like the garden :)
6 Correct 20 ms 668 KB Correct! Azusa and Laika like the garden :)
7 Correct 14 ms 596 KB Correct! Azusa and Laika like the garden :)
8 Correct 13 ms 596 KB Correct! Azusa and Laika like the garden :)
9 Correct 17 ms 688 KB Correct! Azusa and Laika like the garden :)
10 Correct 14 ms 584 KB Correct! Azusa and Laika like the garden :)
11 Correct 14 ms 564 KB Correct! Azusa and Laika like the garden :)
12 Correct 15 ms 700 KB Correct! Azusa and Laika like the garden :)
13 Correct 14 ms 580 KB Correct! Azusa and Laika like the garden :)
14 Correct 15 ms 656 KB Correct! Azusa and Laika like the garden :)
15 Correct 15 ms 596 KB Correct! Azusa and Laika like the garden :)
16 Correct 13 ms 648 KB Correct! Azusa and Laika like the garden :)
17 Correct 17 ms 576 KB Correct! Azusa and Laika like the garden :)
18 Correct 17 ms 668 KB Correct! Azusa and Laika like the garden :)
19 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
20 Correct 5 ms 340 KB Correct! Azusa and Laika like the garden :)
21 Correct 5 ms 436 KB Correct! Azusa and Laika like the garden :)
22 Correct 8 ms 432 KB Correct! Azusa and Laika like the garden :)
23 Correct 8 ms 476 KB Correct! Azusa and Laika like the garden :)
24 Correct 5 ms 340 KB Correct! Azusa and Laika like the garden :)
25 Correct 6 ms 344 KB Correct! Azusa and Laika like the garden :)
26 Correct 7 ms 468 KB Correct! Azusa and Laika like the garden :)
27 Correct 6 ms 468 KB Correct! Azusa and Laika like the garden :)
28 Correct 6 ms 368 KB Correct! Azusa and Laika like the garden :)
29 Correct 5 ms 308 KB Correct! Azusa and Laika like the garden :)
30 Correct 7 ms 436 KB Correct! Azusa and Laika like the garden :)
31 Correct 6 ms 468 KB Correct! Azusa and Laika like the garden :)
32 Correct 8 ms 388 KB Correct! Azusa and Laika like the garden :)
33 Correct 5 ms 340 KB Correct! Azusa and Laika like the garden :)
34 Correct 8 ms 468 KB Correct! Azusa and Laika like the garden :)
35 Correct 6 ms 380 KB Correct! Azusa and Laika like the garden :)
36 Correct 25 ms 844 KB Correct! Azusa and Laika like the garden :)
37 Correct 20 ms 824 KB Correct! Azusa and Laika like the garden :)
38 Correct 20 ms 836 KB Correct! Azusa and Laika like the garden :)
39 Correct 30 ms 744 KB Correct! Azusa and Laika like the garden :)
40 Correct 21 ms 724 KB Correct! Azusa and Laika like the garden :)
41 Correct 20 ms 820 KB Correct! Azusa and Laika like the garden :)
42 Correct 19 ms 744 KB Correct! Azusa and Laika like the garden :)
43 Correct 22 ms 868 KB Correct! Azusa and Laika like the garden :)
44 Correct 22 ms 852 KB Correct! Azusa and Laika like the garden :)
45 Correct 27 ms 724 KB Correct! Azusa and Laika like the garden :)
46 Correct 19 ms 816 KB Correct! Azusa and Laika like the garden :)
47 Correct 20 ms 860 KB Correct! Azusa and Laika like the garden :)
48 Correct 20 ms 840 KB Correct! Azusa and Laika like the garden :)
49 Correct 21 ms 828 KB Correct! Azusa and Laika like the garden :)
50 Correct 20 ms 788 KB Correct! Azusa and Laika like the garden :)
51 Correct 18 ms 724 KB Correct! Azusa and Laika like the garden :)
52 Correct 19 ms 752 KB Correct! Azusa and Laika like the garden :)
53 Correct 21 ms 824 KB Correct! Azusa and Laika like the garden :)
54 Correct 24 ms 852 KB Correct! Azusa and Laika like the garden :)
55 Correct 18 ms 724 KB Correct! Azusa and Laika like the garden :)
56 Correct 27 ms 844 KB Correct! Azusa and Laika like the garden :)
57 Correct 22 ms 768 KB Correct! Azusa and Laika like the garden :)
58 Correct 25 ms 760 KB Correct! Azusa and Laika like the garden :)
59 Correct 28 ms 780 KB Correct! Azusa and Laika like the garden :)
60 Correct 19 ms 852 KB Correct! Azusa and Laika like the garden :)