oj.uz

Submission #498918

# Submission time Handle Problem Language Result Execution time Memory
498918 2021-12-26T17:04:50 Z Josia Gardening (RMI21_gardening) C++14
11 / 100
 20 ms 716 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx")


#include <bits/stdc++.h>

#define int int64_t

using namespace std;





vector<vector<int>> res;
int cnt;


void fillBoarder(int n, int m, int offset) {
    for (int i = offset; i<n+offset; i++) {
        res[i][offset] = cnt;
        res[i][offset+m-1] = cnt;
    }
    for (int i = offset; i<m+offset; i++) {
        res[offset][i] = cnt;
        res[offset+n-1][i] = cnt;
    }
    cnt++;
}

void fillSmaller(int n, int m, int offset) {
    if (n>=m) {
        for (int i = offset; i<m+offset-1; i+=2) {
            res[n+offset-1][i] = cnt;
            res[n+offset-1][i+1] = cnt;
            res[n+offset-2][i] = cnt;
            res[n+offset-2][i+1] = cnt;
            
            cnt++;
        }   
    }
    else {
        for (int i = offset; i<n+offset-1; i+=2) {
            res[i][m+offset-1] = cnt;
            res[i+1][m+offset-1] = cnt;
            res[i][m+offset-2] = cnt;
            res[i+1][m+offset-2] = cnt;

            cnt++;
        }
    }
}


bool solve(int n, int m, int k) {
    cnt = 1;
    // res.clear();
    res.assign(n, vector<int>(m));



    if (n%2 || m%2) return 0;

    if (k > (n*m)/4) return 0;

    if ((n*m)/4 - k == 1) return 0;

    if (k < (n*m/4)/(min(n, m)/2)) return 0;

    if (k == (n*m/4)/(min(n, m)/2)+1 && n>4) return 0;


    int offset = 0;


    while (n != 0 && m != 0) {
        if ((n*2 + (m-2)*2)/4 <= n*m/4 - k + 1) {
            // cout << "Border\n";
            fillBoarder(n, m, offset);
            offset++;
            k--;
            n-=2;
            m-=2;
        }
        else {
            // cout << "Edge\n";
            fillSmaller(n, m, offset);
            k-=min(n, m)/2;
            if (n>=m) n-=2;
            else m-=2;
        }



        // for (auto i: res) {
        //     for (int j: i) {
        //         cout << j << " ";
        //     }
        //     cout << "\n";
        // } cout << "\n";
    }

    return 1;
}






signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int t; cin >> t;

    for (int tc = 0; tc < t; tc++) {
        int n, m, k; cin >> n >> m >> k;


        bool ok = solve(n, m, k);

        if (!ok) {
            cout << "NO\n";
            continue;
        }

        cout << "YES\n";  

        for (auto i: res) {
            for (int j: i) {
                cout << j << " ";
            }
            cout << "\n";
        } 

    }

    // vector<vector<int>> test(8, vector<int>(6));
    // int cnt = 1;
    // fillout(cnt, test, 2, 8, 0);

    // for (auto i: test) {
    //     for (int j: i) {
    //         cerr << j << " ";
    //     }
    //     cerr << "\n";
    // }


    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 716 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 636 KB Correct! Azusa and Laika like the garden :)
3 Correct 13 ms 592 KB Correct! Azusa and Laika like the garden :)

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 716 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 636 KB Correct! Azusa and Laika like the garden :)
3 Correct 13 ms 592 KB Correct! Azusa and Laika like the garden :)
4 Failed 14 ms 544 KB Output contains flowers without two equal neighbours
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Failed 11 ms 716 KB Output contains flowers without two equal neighbours
2 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

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

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 716 KB Correct! Azusa and Laika like the garden :)
2 Correct 10 ms 636 KB Correct! Azusa and Laika like the garden :)
3 Correct 13 ms 592 KB Correct! Azusa and Laika like the garden :)
4 Failed 14 ms 544 KB Output contains flowers without two equal neighbours
5 Halted 0 ms 0 KB -