Submission #579964

#	Time	Username	Problem	Language	Result	Execution time	Memory
579964		FatihSolak	Gardening (RMI21_gardening)	C++17	100 / 100	62 ms	972 KiB

Main

#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<vector<int>> ans;
vector<int> get(int a,int b){
    if(a > b)swap(a,b);
    if(a == 0)return {0};
    vector<int> ret;
    for(int c = b/2;c<=a*b/4;c++){
        bool ok = 1;
        if(a == b && c == a/2 + 1)ok = 0;
        if(c == a*b/4 - 1)ok = 0;
        if(ok)
            ret.push_back(c);
    }
    return ret;
}
void f(int n,int m,int dx,int dy,int k,int col){
    if(n == 0 || m == 0)return;
    //cout << n << " " << m << " " << dx << " " << dy << " " << k << endl;
    vector<pair<int,int>> can = {{2,2},{4,4},{4,6},{6,4},{6,6},{n,m}};
    for(auto circle:can){
        if(circle.first > n || circle.second > m)continue;
        for(auto u:get(circle.first-2,circle.second-2)){
            for(auto c:get(circle.first,m-circle.second)){
                for(auto d:get(n-circle.first,m)){
                    if(u + c + d + 1 == k){
                        for(int i = 0;i<circle.second;i++){
                            ans[0 + dx][i + dy] = col;
                            ans[circle.first - 1 + dx][i + dy] = col;
                        }
                        for(int i = 1;i<circle.first-1;i++){
                            ans[i + dx][0 + dy] = col;
                            ans[i + dx][circle.second - 1 + dy] = col;
                        }
                        col -= 1;
                        f(circle.first-2,circle.second-2,dx + 1,dy + 1,u,col);
                        col -= u;
                        f(circle.first,m-circle.second,dx,dy + circle.second,c,col);
                        col -= c;
                        f(n-circle.first,m,dx + circle.first,dy,d,col);
                        col -= d;
                        return;
                    }
                }
            }   
        }
    }
}
void solve(){
    int n,m,k;
    cin >> n >> m >> k;
    if(n % 2 || m % 2 || n*m/4 < k || k < max(n,m)/2 || k == n*m/4 - 1 || (n == m && k == n/2 + 1)){
        cout << "NO" << "\n";
        return;
    }
    cout << "YES" << "\n";
    ans = vector<vector<int>>(n,vector<int>(m,0));
    f(n,m,0,0,k,k);
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cout << ans[i][j] << " ";
        }
        cout << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

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