Submission #498916

#	Time	Username	Problem	Language	Result	Execution time	Memory
498916		Josia	Gardening (RMI21_gardening)	C++14	5 / 100	23 ms	708 KiB

Main

#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) 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 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 18
• Subtask 5: 0 / 39
• Subtask 6: 0 / 22