이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
using namespace std;
const int N = 2e5 + 5;
int col = 0;
vector < int > ans[N];
inline pair < int , int > get(int n, int m) {
assert(n % 2 == 0);
assert(m % 2 == 0);
if (n == 0 || m == 0) return {0, 0};
return {max(n, m) / 2, n * m / 4};
}
vector < pair < int , int > > c2;
vector < pair < pair < int , int > , pair < int , int > > > car;
inline void solve(int x, int y, int k, int lenx, int leny) {
if (!k || !lenx || !leny) return;
if (lenx > 2 && leny > 2) {
int newk = k - 1;
pair < int , int > lim = get(lenx - 2, leny - 2);
if (lim.f <= newk && newk <= lim.s && newk != lim.s - 1) {
if (!(lenx == leny && newk == lim.f + 1)) {
car.pb({{x, y}, {x + lenx - 1, y + leny - 1}});
solve(x + 1, y + 1, newk, lenx - 2, leny - 2);
return;
}
}
}
if (lenx >= 2) {
int newk = k - leny / 2;
pair < int , int > lim = get(lenx - 2, leny);
if (lim.f <= newk && newk <= lim.s && newk != lim.s - 1) {
if (!(lenx - 2 == leny && newk == lim.f + 1)) {
for (int j = y; j < y + leny; j += 2)
c2.pb({x, j});
solve(x + 2, y, newk, lenx - 2, leny);
return ;
}
}
}
if (leny >= 2) {
int newk = k - lenx / 2;
pair < int , int > lim = get(lenx, leny - 2);
if (lim.f <= newk && newk <= lim.s && newk != lim.s - 1) {
if (!(lenx == leny - 2 && newk == lim.f + 1)) {
for (int i = x; i < x + lenx; i += 2)
c2.pb({i, y});
solve(x, y + 2, newk, lenx, leny - 2);
return ;
}
}
}
for (int i = 4; i <= lenx / 2; i += 2) {
pair < int , int > liml = get(i, leny);
pair < int , int > limr = get(lenx - i, leny);
int kl = k - limr.s, kr = limr.s;
if (liml.f <= kl && kl <= liml.s && kl != liml.s - 1) {
if (!(i == leny && kl == liml.f + 1)) {
solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
return ;
}
}
kl = liml.s, kr = k - liml.s;
if (limr.f <= kr && kr <= limr.s && kr != limr.s - 1) {
if (!(lenx - i == leny && kr == limr.f + 1)) {
solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
return ;
}
}
kl = k - limr.f, kr = limr.f;
if (liml.f <= kl && kl <= liml.s && kl != liml.s - 1) {
if (!(i == leny && kl == liml.f + 1)) {
solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
return ;
}
}
kl = liml.f, kr = k - liml.f;
if (limr.f <= kr && kr <= limr.s && kr != limr.s - 1) {
if (!(lenx - i == leny && kr == limr.f + 1)) {
solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
return ;
}
}
liml.s -= 2;
limr.s -= 2;
if (i == leny) liml.f += 2;
if (lenx - i == leny) limr.f += 2;
int l = liml.f, r = liml.s, mid, res = -1;
while (l <= r) {
mid = (l + r) / 2;
if (k - mid <= limr.s) {
res = k, r = mid - 1;
}
else {
l = mid + 1;
}
}
if (res == -1) continue;
kl = res, kr = k - res;
if (liml.f <= kl && kl <= liml.s && limr.f <= kr && kr <= limr.s) {
solve(x, y, kl, i, leny), solve(x + i, y, kr, lenx - i, leny);
return ;
}
}
}
inline void solve() {
int n, m, k;
col = 0;
cin >> n >> m >> k;
if (n == m && k == max(n, m) / 2 + 1) {
cout << "NO\n";
return ;
}
if (n % 2 || m % 2 || 2 * k < max(n, m) || n * m < 4 * k || k == n * m / 4 - 1) {
cout << "NO\n";
return ;
}
c2.clear();
car.clear();
solve(1, 1, k, n, m);
int ans[n + 10][m + 10];
for (int t = 0; t < c2.size(); ++t) {
++col;
int x = c2[t].f, y = c2[t].s;
for (int i = x; i < x + 2; ++i)
for (int j = y; j < y + 2; ++j)
ans[i][j] = col;
}
for (int t = 0; t < car.size(); ++t) {
++col;
int x = car[t].f.f, y = car[t].f.s;
int X = car[t].s.f, Y = car[t].s.s;
for (int i = x; i <= X; ++i) {
ans[i][y] = ans[i][Y] = col;
}
for (int j = y; j <= Y; ++j) {
ans[x][j] = ans[X][j] = col;
}
}
cout << "YES\n";
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
cout << ans[i][j] << " ";
cout << "\n";
}
}
main () {
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int t;
cin >> t;
while (t--) {
solve();
}
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void solve()':
Main.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (int t = 0; t < c2.size(); ++t) {
| ~~^~~~~~~~~~~
Main.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int t = 0; t < car.size(); ++t) {
| ~~^~~~~~~~~~~~
Main.cpp: At global scope:
Main.cpp:167:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
167 | main () {
| ^~~~
# | 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... |