oj.uz

Submission #647958

# Submission time Handle Problem Language Result Execution time Memory
647958 2022-10-04T17:09:53 Z ovidiush11 Gardening (RMI21_gardening) C++14
100 / 100
 124 ms 980 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

void draw1(ll n,ll m,ll v)
{
    if(v != 0){
    for(ll i = 1;i <= v;i++)cout<<i<<" ";
    for(ll i = 0;i < m;i++)cout<<v<<" ";
    for(ll i = v;i > 0;i--)cout<<i<<" ";
    cout<<endl;}
    ll x = v+1,y = v+1;
    for(ll i = 0;i < n;i++)
    {
        for(ll j = 1;j <= v;j++)cout<<j<<" ";
        for(ll j = 0;j < m;j+=2)
        {
            cout<<x<<" "<<x<<" ";
            x++;
        }
        for(ll j = v;j > 0;j--)cout<<j<<" ";
        swap(x,y);
        cout<<endl;
    }
    if(v != 0){
    for(ll i = 1;i <= v;i++)cout<<i<<" ";
    for(ll i = 0;i < m;i++)cout<<v<<" ";
    for(ll i = v;i > 0;i--)cout<<i<<" ";
    cout<<endl;}
}

ll line(ll n,ll m,ll v,ll r,ll y){
    for(ll i = 1;i <= v;i++)cout<<i<<" ";
    for(ll i = 0;i < r;i++)cout<<v+1<<" ";
    for(ll i = r;i < m;i+=2)
    {
        cout<<y<<" "<<y<<" ";
        y++;
    }
    for(ll i = v;i > 0;i--)cout<<i<<" ";
    cout<<endl;
    return y;
}

pair<ll,ll> fline(ll n,ll m,ll v,ll r,ll x,ll y){
    for(ll i = 1;i <= v;i++)cout<<i<<" ";
    for(ll i = 0;i < 4;i++)cout<<v+1<<" ";
    for(ll i = 5;i < r-1;i+=2)
    {
        cout<<x<<" "<<x<<" ";
        x++;
    }
    cout<<v<<" ";
    for(ll i = r;i < m;i+=2)
    {
        cout<<y<<" "<<y<<" ";
        y++;
    }
    for(ll i = v-1;i > 0;i--)cout<<i<<" ";
    cout<<endl;
    swap(x,y);

    for(ll i = 1;i <= v;i++)cout<<i<<" ";
    cout<<v+1<<" "<<v+2<<" "<<v+2<<" "<<v+1<<" ";
    for(ll i = 5;i < r-1;i+=2)
    {
        cout<<x<<" "<<x<<" ";
        x++;
    }
    cout<<v<<" ";
    for(ll i = r;i < m;i+=2)
    {
        cout<<y<<" "<<y<<" ";
        y++;
    }
    for(ll i = v-1;i > 0;i--)cout<<i<<" ";
    cout<<endl;
    swap(x,y);

    for(ll i = 1;i <= v;i++)cout<<i<<" ";
    cout<<v+1<<" "<<v+2<<" "<<v+2<<" "<<v+1<<" ";
    for(ll i = 5;i < r-1;i+=2)
    {
        cout<<x<<" "<<x<<" ";
        x++;
    }
    cout<<v<<" ";
    for(ll i = r;i < m;i+=2)
    {
        cout<<y<<" "<<y<<" ";
        y++;
    }
    for(ll i = v-1;i > 0;i--)cout<<i<<" ";
    cout<<endl;
    swap(x,y);

    for(ll i = 1;i <= v;i++)cout<<i<<" ";
    for(ll i = 0;i < 4;i++)cout<<v+1<<" ";
    for(ll i = 5;i < r-1;i+=2)
    {
        cout<<x<<" "<<x<<" ";
        x++;
    }
    cout<<v<<" ";
    for(ll i = r;i < m;i+=2)
    {
        cout<<y<<" "<<y<<" ";
        y++;
    }
    for(ll i = v-1;i > 0;i--)cout<<i<<" ";
    cout<<endl;
    swap(x,y);

    pair<ll,ll> s;
    s.first = x;
    s.second = y;
    return s;
}

void draw2(ll n,ll m,ll v)
{
    ll r,d,x = v + 3,y = v + 3;
    if(n >= 8){
        r = m;
        d = n - 2;
    }
    else{
        r = m - 2;
        d = n;
    }

    y = line(n,m,v-1,r,y);
    swap(x,y);
    pair<ll,ll> s = fline(n,m,v,r,x,y);
    x = s.first;y = s.second;
    for(ll i = 5;i < d-1;i++){
        for(ll j = 1;j <= v;j++)cout<<j<<" ";
        for(ll j = 1;j < r-1;j+=2)
        {
            cout<<x<<" "<<x<<" ";
            x++;
        }
        for(ll j = r;j < m;j+=2)
        {
            cout<<y<<" "<<y<<" ";
            y++;
        }
        for(ll j = v;j > 0;j--)cout<<j<<" ";
        cout<<endl;
        swap(x,y);
    }

    y = line(n,m,v-1,r,y);
    swap(x,y);

    for(ll i = d;i < n;i++){
        for(ll j = 1;j < v;j++)cout<<j<<" ";
        for(ll j = 0;j < m;j+=2)
        {
            cout<<y<<" "<<y<<" ";
            y++;
        }
        for(ll j = v-1;j > 0;j--)cout<<j<<" ";
        cout<<endl;
        swap(x,y);
    }
    return ;
}

void draw3(ll n,ll m,ll v,ll k)
{
    if(v != 0){
        for(ll i = 1;i <= v;i++)cout<<i<<" ";
        for(ll i = 0;i < m;i++)cout<<v<<" ";
        for(ll i = v;i > 0;i--)cout<<i<<" ";
        cout<<endl;
    }

    ll r,d,x = v+2,y = v+2;
    if(k * 2 >= m){
        r = m;
        k -= m / 2;
        d = k * 2 + 4;
    }
    else{
        d = 4;
        r = k * 2;
    }

    y = line(n,m,v,r,y);
    swap(x,y);
    for(ll i = 1;i < d-1;i++){
        for(ll j = 1;j <= v+1;j++)cout<<j<<" ";
        for(ll j = 1;j < r-1;j+=2)
        {
            cout<<x<<" "<<x<<" ";
            x++;
        }
        cout<<v+1<<" ";
        for(ll j = r;j < m;j+=2)
        {
            cout<<y<<" "<<y<<" ";
            y++;
        }
        for(ll j = v;j > 0;j--)cout<<j<<" ";
        cout<<endl;
        swap(x,y);
    }
    y = line(n,m,v,r,y);
    swap(x,y);


    for(ll i = d;i < n;i++){
        for(ll j = 1;j <= v;j++)cout<<j<<" ";
        for(ll j = 0;j < m;j+=2)
        {
            cout<<y<<" "<<y<<" ";
            y++;
        }
        for(ll j = v;j > 0;j--)cout<<j<<" ";
        cout<<endl;
        swap(x,y);
    }

    if(v != 0){
        for(ll i = 1;i <= v;i++)cout<<i<<" ";
        for(ll i = 0;i < m;i++)cout<<v<<" ";
        for(ll i = v;i > 0;i--)cout<<i<<" ";
        cout<<endl;
    }
}

void draw(ll n,ll m,ll k,ll v)
{
    for(ll i = 1;i < v;i++)
    {
        for(ll j = 0;j < i;j++)cout<<j+1<<" ";
        for(ll j = i;j < m-i;j++)cout<<i<<" ";
        for(ll j = m-i;j < m;j++)cout<<m - j<<" ";
        cout<<endl;
    }
    ll h = v + (n - v * 2) * (m - v * 2) / 4;

    if(h == k)draw1(n-v*2,m-v*2,v);
    else if(h - k == 1)draw2(n-v*2+2,m-v*2+2,v);
    else draw3(n-v*2,m-v*2,v,h-k);

    for(ll i = v-1;i > 0;i--)
    {
        for(ll j = 0;j < i;j++)cout<<j+1<<" ";
        for(ll j = i;j < m-i;j++)cout<<i<<" ";
        for(ll j = m-i;j < m;j++)cout<<m - j<<" ";
        cout<<endl;
    }
    return ;
}

void solve()
{
    ll n,m,k;
    cin>>n>>m>>k;
    if(n % 2 == 1 || m % 2 == 1)
    {
        cout<<"NO"<<endl;
        return ;
    }
    ll x = (n - min(n,m) + 2) * (m - min(n,m) + 2) / 4 + min(n,m) / 2 - 1,y = n*m / 4;
    if(k > y || k < x)cout<<"NO"<<endl;
    else if(n == m && k == x+1)cout<<"NO"<<endl;
    else if(k == y - 1)cout<<"NO"<<endl;
    else
    {
        cout<<"YES"<<endl;
        ll v = -1;
        while(y >= k)
        {
            v++;
            if(v * 2 == min(n,m))break;
            y = (n - (v + 1) * 2) * (m - (v + 1) * 2) / 4 + (v + 1);
        }
        draw(n,m,k,v);
    }
    return ;
}

int main()
{
    ll t;
    cin>>t;
    while(t--)solve();
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 980 KB Correct! Azusa and Laika like the garden :)
2 Correct 23 ms 616 KB Correct! Azusa and Laika like the garden :)
3 Correct 22 ms 596 KB Correct! Azusa and Laika like the garden :)

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 980 KB Correct! Azusa and Laika like the garden :)
2 Correct 23 ms 616 KB Correct! Azusa and Laika like the garden :)
3 Correct 22 ms 596 KB Correct! Azusa and Laika like the garden :)
4 Correct 21 ms 588 KB Correct! Azusa and Laika like the garden :)
5 Correct 21 ms 508 KB Correct! Azusa and Laika like the garden :)

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 520 KB Correct! Azusa and Laika like the garden :)
2 Correct 14 ms 596 KB Correct! Azusa and Laika like the garden :)
3 Correct 14 ms 468 KB Correct! Azusa and Laika like the garden :)
4 Correct 17 ms 596 KB Correct! Azusa and Laika like the garden :)
5 Correct 15 ms 516 KB Correct! Azusa and Laika like the garden :)
6 Correct 14 ms 536 KB Correct! Azusa and Laika like the garden :)
7 Correct 17 ms 596 KB Correct! Azusa and Laika like the garden :)
8 Correct 16 ms 468 KB Correct! Azusa and Laika like the garden :)
9 Correct 18 ms 552 KB Correct! Azusa and Laika like the garden :)
10 Correct 16 ms 596 KB Correct! Azusa and Laika like the garden :)
11 Correct 14 ms 596 KB Correct! Azusa and Laika like the garden :)
12 Correct 14 ms 468 KB Correct! Azusa and Laika like the garden :)
13 Correct 14 ms 468 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 6 ms 340 KB Correct! Azusa and Laika like the garden :)
3 Correct 5 ms 384 KB Correct! Azusa and Laika like the garden :)
4 Correct 11 ms 428 KB Correct! Azusa and Laika like the garden :)
5 Correct 8 ms 392 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 340 KB Correct! Azusa and Laika like the garden :)
8 Correct 8 ms 340 KB Correct! Azusa and Laika like the garden :)
9 Correct 7 ms 468 KB Correct! Azusa and Laika like the garden :)
10 Correct 7 ms 384 KB Correct! Azusa and Laika like the garden :)
11 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
12 Correct 7 ms 340 KB Correct! Azusa and Laika like the garden :)
13 Correct 6 ms 360 KB Correct! Azusa and Laika like the garden :)
14 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
15 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
16 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
17 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 980 KB Correct! Azusa and Laika like the garden :)
2 Correct 23 ms 616 KB Correct! Azusa and Laika like the garden :)
3 Correct 22 ms 596 KB Correct! Azusa and Laika like the garden :)
4 Correct 21 ms 588 KB Correct! Azusa and Laika like the garden :)
5 Correct 21 ms 508 KB Correct! Azusa and Laika like the garden :)
6 Correct 16 ms 520 KB Correct! Azusa and Laika like the garden :)
7 Correct 14 ms 596 KB Correct! Azusa and Laika like the garden :)
8 Correct 14 ms 468 KB Correct! Azusa and Laika like the garden :)
9 Correct 17 ms 596 KB Correct! Azusa and Laika like the garden :)
10 Correct 15 ms 516 KB Correct! Azusa and Laika like the garden :)
11 Correct 14 ms 536 KB Correct! Azusa and Laika like the garden :)
12 Correct 17 ms 596 KB Correct! Azusa and Laika like the garden :)
13 Correct 16 ms 468 KB Correct! Azusa and Laika like the garden :)
14 Correct 18 ms 552 KB Correct! Azusa and Laika like the garden :)
15 Correct 16 ms 596 KB Correct! Azusa and Laika like the garden :)
16 Correct 14 ms 596 KB Correct! Azusa and Laika like the garden :)
17 Correct 14 ms 468 KB Correct! Azusa and Laika like the garden :)
18 Correct 14 ms 468 KB Correct! Azusa and Laika like the garden :)
19 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
20 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
21 Correct 5 ms 384 KB Correct! Azusa and Laika like the garden :)
22 Correct 11 ms 428 KB Correct! Azusa and Laika like the garden :)
23 Correct 8 ms 392 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 340 KB Correct! Azusa and Laika like the garden :)
26 Correct 8 ms 340 KB Correct! Azusa and Laika like the garden :)
27 Correct 7 ms 468 KB Correct! Azusa and Laika like the garden :)
28 Correct 7 ms 384 KB Correct! Azusa and Laika like the garden :)
29 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
30 Correct 7 ms 340 KB Correct! Azusa and Laika like the garden :)
31 Correct 6 ms 360 KB Correct! Azusa and Laika like the garden :)
32 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
33 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
34 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
35 Correct 6 ms 340 KB Correct! Azusa and Laika like the garden :)
36 Correct 21 ms 692 KB Correct! Azusa and Laika like the garden :)
37 Correct 22 ms 724 KB Correct! Azusa and Laika like the garden :)
38 Correct 22 ms 724 KB Correct! Azusa and Laika like the garden :)
39 Correct 22 ms 804 KB Correct! Azusa and Laika like the garden :)
40 Correct 19 ms 676 KB Correct! Azusa and Laika like the garden :)
41 Correct 19 ms 696 KB Correct! Azusa and Laika like the garden :)
42 Correct 21 ms 628 KB Correct! Azusa and Laika like the garden :)
43 Correct 21 ms 740 KB Correct! Azusa and Laika like the garden :)
44 Correct 19 ms 716 KB Correct! Azusa and Laika like the garden :)
45 Correct 20 ms 592 KB Correct! Azusa and Laika like the garden :)
46 Correct 20 ms 704 KB Correct! Azusa and Laika like the garden :)
47 Correct 21 ms 748 KB Correct! Azusa and Laika like the garden :)
48 Correct 23 ms 716 KB Correct! Azusa and Laika like the garden :)
49 Correct 23 ms 704 KB Correct! Azusa and Laika like the garden :)
50 Correct 21 ms 724 KB Correct! Azusa and Laika like the garden :)
51 Correct 20 ms 600 KB Correct! Azusa and Laika like the garden :)
52 Correct 26 ms 620 KB Correct! Azusa and Laika like the garden :)
53 Correct 22 ms 744 KB Correct! Azusa and Laika like the garden :)
54 Correct 26 ms 668 KB Correct! Azusa and Laika like the garden :)
55 Correct 19 ms 724 KB Correct! Azusa and Laika like the garden :)
56 Correct 23 ms 700 KB Correct! Azusa and Laika like the garden :)
57 Correct 21 ms 776 KB Correct! Azusa and Laika like the garden :)
58 Correct 23 ms 724 KB Correct! Azusa and Laika like the garden :)
59 Correct 23 ms 680 KB Correct! Azusa and Laika like the garden :)
60 Correct 20 ms 680 KB Correct! Azusa and Laika like the garden :)