Submission #645978

#	Time	Username	Problem	Language	Result	Execution time	Memory
645978		MadokaMagicaFan	Gardening (RMI21_gardening)	C++14	5 / 100	79 ms	704 KiB

Main

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;

#define forn(i,n)   for(int i = 0; i < n; ++i)
#define pb          push_back
#define sz(v)       ((int)((v).size()))

int frm = 0;

void
doframe(int t, int x, int y, int w, int h, vector<vi> &a)
{

    if (h == -1) {
        h = sz(a[0])-y-frm;
        ++frm;
    }
    for (int i = 0; i < w; ++i) {
        a[x+i][y] = t;
        a[x+i][y+h-1] = t;
    }

    for (int i = 0; i < h; ++i) {
        a[x][y+i] = t;
        a[x+w-1][y+i] = t;
    }
    return;
}

struct line{
    int w;
    int f;
};

void
solve()
{
    int n, m, k;
    frm = 0;

    cin >> n >> m >> k;
    bool t = 0;
    vector<vi> ans;
    int v, c;
    int w, h;
    int o= 0;
    int oy, ox;
    int tval;
    int cnt = 0;
    vector<line> l;

    if (n & 1)
        goto untrue;
    if (m & 1)
        goto untrue;

    n >>= 1;
    m >>= 1;


    if (n > k)
        goto untrue;
    if (m > k)
        goto untrue;


    for (int i = 0; i < n && i <= m; ++i) {
        if (k % (n-i) == i && (k/(n-i)) <= m-i && (k/(n-i)) * (n-i) >= m-i) {
            t = 1;
            v = 0;
            c = i;
            break;
        }
    }

    for (int i = 0; i < m && i <= n; ++i) {
        if (k % (m-i) == i && (k/(m-i)) <= n-i && (k/(m-i)) * (m-i) >= n-i) {
            v = 1;
            c = i;
            t = 1;
            break;
        }
    }

    if (!t)
        goto solvetwo;

    /* goto solvetwo; */
    cout << "YES\n";

    if (!v)
        swap(n,m);
    ans.assign(n<<1,{});

    for (int i = 0; i < (n<<1); ++i) {
        ans[i].assign(m<<1,0);
    }

    for (int i = 0; i < c; ++i) {
        doframe(i+1, i, i, (n-i)<<1, (m-i)<<1, ans);
    }

    w = n - c;
    h = m - c;
    k -= c;
    o = c;
    oy = c;
    ox = c;

    for (int i = 0; i < k/h; ++i) {
        o = min(w+i-k/h, h-1);
        /* if (w > ((k/h) - i)) { */
            for (int j = 0; j < o; ++j) {
                doframe(i*h + c+1 +j, ox+j, oy+j, (o-j+1)<<1, (h-j)<<1, ans);
            }
        /* } */

        for (int j = o; j < h; ++j) {
            doframe(i*h+c+1+j, ox+o, oy-o+2*j, 2, 2, ans);
        }
        w -= (1 + o);
        ox += ((1 + o)<<1);
        /* w -= 1kkkkkkkk */
    }

    if (!v)
        swap(n,m);

    for (int i = 0; i < (n<<1); ++i) {
        for (int j = 0; j < (m<<1); ++j) {
            if (!v)
                cout << ans[j][i] << ' ';
            else
                cout << ans[i][j] << ' ';
        }
        cout << endl;
    }


    return;
    solvetwo:
    for (int i = 0; i < (k/n); ++i) {
        l.pb({n,0});
    }
    if (k % n)
        l.pb({k % n, 0});

    if (sz(l) > m)
        goto untrue;

    while (l.back().w + l.back().f < n) {
        o = n - l.back().w - l.back().f;

        if (sz(l)-1 >= o)
            o = sz(l)-2;
        if (l[sz(l)-2].w < 2)
            goto untrue;
        for (int i = sz(l)-o-2; i < sz(l)-1; ++i) {
            l[i].w--;
            l[i].f++;
        }
        l.back().w += (o-1);
        l.back().f++;
    }

    o = l.back().f;
    for (int i = 0; i < sz(l); ++i) {
        o += l[i].w;
    }

    if (o < m)
        goto untrue;
    if (sz(l) + l.back().f > m)
        goto untrue;

    ox = oy = 0;

    ans.assign(n<<1,{});

    for (int i = 0; i < (n<<1); ++i) {
        ans[i].assign(m<<1,0);
    }

    o = 0;
    h = m;
    w = n;
    for (int i = 0; i < sz(l)-1; ++i) {
        if (l[i].w + l[i].f != n)
            assert(l[i].w + l[i].f == n);
    }
    for (int i = 0; i < sz(l); ++i) {
        if (l[i].f > o) {
            for (; o < l[i].f; ++o) {
                doframe(++cnt,ox,oy,w<<1, -1, ans);
                    ++ox, ++oy;
                --h;
                --w;
            }
        }


        /* assert(l[i].w == w); */
        o = min(h-(sz(l)-i) + o - l.back().f, w-1);
        /* if (w > ((k/h) - i)) { */
            for (int j = 0; j < o; ++j) {
                doframe(++cnt, ox+j, oy+j, (w-j)<<1, (o-j+1)<<1, ans);
            }
        /* } */

        for (int j = o; j < w; ++j) {
            doframe(++cnt, ox-o+2*j, oy+o, 2, 2, ans);
        }
        h -= (1 + o);
        oy += ((1 + o)<<1);
        /* w -= 1kkkkkkkk */

        o = l[i].f;
    }

    /* assert(cnt <= n); */
    cout << "YES\n";


    for (int i = 0; i < (n<<1); ++i) {
        for (int j = 0; j < (m<<1); ++j) {
                cout << ans[i][j] << ' ';
        }
        cout << endl;
    }
    return;

    untrue:
    cout << "NO\n";
    return;
}

int32_t
main(int argc, char *argv[])
{
    if (argc>1)
        freopen(argv[1], "r", stdin);
    else
        ios_base::sync_with_stdio(0), cin.tie(0);
    int t;

    cin >> t;

    while (t--)
        solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:53:9: warning: unused variable 'tval' [-Wunused-variable]
   53 |     int tval;
      |         ^~~~
Main.cpp: In function 'int32_t main(int, char**)':
Main.cpp:246:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  246 |         freopen(argv[1], "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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