This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 ) {
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++;
} else
break;
}
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); ++i) {
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:248:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
248 | freopen(argv[1], "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |