Submission #638880

#	Time	Username	Problem	Language	Result	Execution time	Memory
638880		Alexandruabcde	Gardening (RMI21_gardening)	C++14	100 / 100	31 ms	24668 KiB

Main

#include <bits/stdc++.h>
#define DEBUG 0

using namespace std;

typedef pair <int, int> PII;
typedef pair <int, pair <int, int> > PIII;
constexpr int NMAX = 1005;

///4 10 6

int N, M, K;

vector <PIII> Values[NMAX][NMAX];

void Precompute () {
    for (int i = 2; i <= N; i += 2) {
        for (int j = 2; j <= M; j += 2) {
            if (i == 2) {
                Values[i][j].push_back({j/2, {0, 0}});

                continue;
            }

            if (j == 2) {
                Values[i][j].push_back({i/2, {0, 0}});

                continue;
            }

            vector <PIII> aux;

            for (auto it : Values[i-2][j-2]) {
                aux.push_back({it.first + 1, {i-2, j-2}});
            }

            for (auto it : Values[i-2][j]) {
                aux.push_back({it.first + j/2, {i-2, j}});
            }

            for (auto it : Values[i][j-2]) {
                aux.push_back({it.first + i/2, {i, j-2}});
            }

            sort(aux.begin(), aux.end());

            for (auto it : aux) {
                if (Values[i][j].empty() || Values[i][j].back().first != it.first)
                    Values[i][j].push_back(it);

                if (!Values[i][j].empty() && Values[i][j].back().first == it.first) {
                    Values[i][j].pop_back();

                    Values[i][j].push_back(it);
                }
            }
        }
    }
}

vector <vector <int> > ans;

void Complete_Border (PII &stsus, PII &drjos, int &who) {
    for (int i = stsus.first; i <= drjos.first; ++ i )
        ans[i][stsus.second] = ans[i][drjos.second] = who;
    for (int i = stsus.second ; i <= drjos.second; ++ i )
        ans[stsus.first][i] = ans[drjos.first][i] = who;

    ++ who;

    stsus.first ++, stsus.second ++;
    drjos.first --, drjos.second --;
}

void Complete_Column (PII &stsus, PII &drjos, int &who) {
    for (int i = stsus.first; i < drjos.first; i += 2) {
        ans[i][drjos.second] = ans[i+1][drjos.second] = who;
        ans[i][drjos.second-1] = ans[i+1][drjos.second-1] = who;

        ++ who;
    }

    drjos.second -= 2;
}

void Complete_Line (PII &stsus, PII &drjos, int &who) {
    for (int i = stsus.second; i < drjos.second; i += 2) {
        ans[drjos.first][i] = ans[drjos.first][i+1] = who;
        ans[drjos.first-1][i] = ans[drjos.first-1][i+1] = who;

        ++ who;
    }

    drjos.first -= 2;
}

void Do_Testcase() {
    cin >> N >> M >> K;

    ans.resize(N);
    for (auto &it : ans)
        it.resize(M);

    if (N % 2 == 1 || M % 2 == 1) {
        cout << "NO\n";
        return;
    }

    int Min_K_Pos = max(N, M) / 2;
    int Max_K_Pos = N * M / 4;

    if (K < Min_K_Pos || K > Max_K_Pos || (K == Min_K_Pos + 1 && N == M) || K == Max_K_Pos - 1) {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";

    int who = 1;
    PII stsus = {0, 0};
    PII drjos = {N-1, M-1};

    int NrLin = N, NrCol = M;
    while (NrLin > 2 && NrCol > 2) {
        int Min_K_Pos = max(NrLin, NrCol) / 2;
        int cnt22 = min(NrLin, NrCol) / 2 - 1;
        int cnt20 = (NrLin - NrCol) / 2 + 1;

        if (NrLin == NrCol) {
            if (K <= Min_K_Pos + cnt22) {
                Complete_Border(stsus, drjos, who);
                -- K;
            }
            else {
                Complete_Column(stsus, drjos, who);
                K -= (NrLin / 2);
            }
        }
        else {
            if (NrCol > NrLin + 2) {
                if (K <= Min_K_Pos + cnt22 - 1) {
                    Complete_Border(stsus, drjos, who);
                    -- K;
                }
                else {
                    Complete_Column(stsus, drjos, who);
                    K -= (NrLin / 2);
                }
            }
            else if (NrCol == NrLin + 2) {
                if (K <= Min_K_Pos + cnt22 - 1 || K == Min_K_Pos + cnt22 + 1) {
                    Complete_Border(stsus, drjos, who);
                    -- K;
                }
                else {
                    Complete_Column(stsus, drjos, who);
                    K -= (NrLin / 2);
                }
            }
            else {
                if (NrLin == NrCol + 2) {
                    if (K <= Min_K_Pos + cnt22 - 1 || K == Min_K_Pos + cnt22 + 1) {
                        Complete_Border(stsus, drjos, who);
                        -- K;
                    }
                    else {
                        if (K == Min_K_Pos + cnt22) {
                            Complete_Line(stsus, drjos, who);
                            K -= (NrCol / 2);
                        }
                        else {
                            Complete_Column(stsus, drjos, who);
                            K -= (NrLin / 2);
                        }
                    }
                }
                else {
                    if (K <= Min_K_Pos + cnt22 - 1) {
                        Complete_Border(stsus, drjos, who);
                        -- K;
                    }
                    else if (K <= Min_K_Pos + cnt22 + cnt20 - 1) {
                        Complete_Line(stsus, drjos, who);
                        K -= (NrCol / 2);
                    }
                    else {
                        Complete_Column(stsus, drjos, who);
                        K -= (NrLin / 2);
                    }
                }
            }
        }

        NrLin = drjos.first - stsus.first + 1;
        NrCol = drjos.second - stsus.second + 1;
    }

    if (NrLin == 2) {
        Complete_Line(stsus, drjos, who);
    }
    else Complete_Column(stsus, drjos, who);

    for (int i = 0; i < N; ++ i ) {
        for (int j = 0; j < M; ++ j )
            cout << ans[i][j] << " ";
        cout << '\n';
    }

    ans.clear();
}

void Solve () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    for (; T; -- T )
        Do_Testcase();
}

int main () {
    if (!DEBUG) {
        Solve();
        return 0;
    }

    cin >> N >> M;


    Precompute();

    for (auto it : Values[N][M]) {
        int cnt = it.first;
        int i = it.second.first;
        int j = it.second.second;

        cout << cnt << " " << i << " " << j << '\n';
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10
• Subtask 4: 18 / 18
• Subtask 5: 39 / 39
• Subtask 6: 22 / 22