QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#184198 | #6791. Domino Tiling | ucup-team004# | AC ✓ | 18ms | 3668kb | C++20 | 4.9kb | 2023-09-20 15:01:15 | 2023-09-20 15:01:16 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
std::vector<std::vector<int>> transpose(const std::vector<std::vector<int>> &a) {
if (a.empty()) {
return {};
}
int n = a.size(), m = a[0].size();
std::vector<std::vector<int>> b(m, std::vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[j][i] = a[i][j];
}
}
return b;
}
std::vector<std::vector<int>> get(int n, int m) {
if (n * m % 2 == 1) {
return {};
}
std::vector a(n, std::vector<int>(m));
int tot = 0;
auto work = [&](int u, int d, int l, int r) {
while (u < d && l < r) {
for (int i = l; i < r; i += 2) {
if (u >= 0) {
a[u][i] = a[u][i + 1] = ++tot;
}
if (d <= n) {
a[d - 1][i] = a[d - 1][i + 1] = ++tot;
}
}
u++, d--;
for (int i = u; i < d; i += 2) {
a[i][l] = a[i + 1][l] = ++tot;
a[i][r - 1] = a[i + 1][r - 1] = ++tot;
}
l++, r--;
}
};
if (n <= m) {
if (n % 2 == 0) {
for (int k = 1; ; k++) {
int L = (n - 2) * k + k - 1;
if (L > m) {
break;
}
int R = L + 2 + 2 * k;
if (m <= R) {
int lng = std::min(k, (m - L) / 2);
int sht = k - lng;
int bnd = m - L - 2 * lng;
int l = 0;
if (bnd) {
bnd--;
for (int i = 0; i < n; i += 2) {
a[i][l] = a[i + 1][l] = ++tot;
}
l++;
}
for (int j = 0; j < k; j++) {
if (j) {
for (int i = 0; i < n; i += 2) {
a[i][l] = a[i + 1][l] = ++tot;
}
l++;
}
if (lng) {
lng--;
work(0, n, l, l + n);
l += n;
} else {
sht--;
work(0, n, l, l + n - 2);
l += n - 2;
}
}
if (bnd) {
bnd--;
for (int i = 0; i < n; i += 2) {
a[i][l] = a[i + 1][l] = ++tot;
}
l++;
}
return a;
}
}
} else {
for (int k = 1; ; k++) {
int L = (n - 1) * k;
if (L > m) {
break;
}
int R = L + 2 * k;
if (m <= R) {
int lng = (m - L) / 2;
int sht = k - lng;
int l = 0;
for (int j = 0; j < k; j++) {
if (lng) {
lng--;
if (j % 2) {
work(-1, n, l, l + n + 1);
} else {
work(0, n + 1, l, l + n + 1);
}
l += n + 1;
} else {
sht--;
if (j % 2) {
work(-1, n, l, l + n - 1);
} else {
work(0, n + 1, l, l + n - 1);
}
l += n - 1;
}
}
return a;
}
}
}
} else {
return transpose(get(m, n));
}
return {};
}
void solve() {
int n, m;
std::cin >> n >> m;
auto ans = get(n, m);
if (ans.empty()) {
std::cout << "Impossible!\n";
return;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
std::cout << ans[i][j] << " \n"[j == m - 1];
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m - 1; j++) {
assert(ans[i][j] == ans[i][j + 1] || ans[i][j + 1] == ans[i + 1][j + 1] || ans[i + 1][j + 1] == ans[i + 1][j] || ans[i + 1][j] == ans[i][j]);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3524kb
input:
3 1 1 4 3 4 4
output:
Impossible! 1 3 3 1 5 6 2 5 6 2 4 4 1 1 3 3 5 7 7 6 5 8 8 6 2 2 4 4
result:
ok 3 cases
Test #2:
score: 0
Accepted
time: 18ms
memory: 3668kb
input:
1839 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21 2 22 2 2...
output:
Impossible! 1 1 Impossible! 1 1 2 2 Impossible! 1 1 2 2 3 3 Impossible! 1 1 2 2 3 3 4 4 Impossible! 1 1 2 2 3 3 4 4 5 5 Impossible! 1 1 2 2 3 3 4 4 5 5 6 6 Impossible! 1 1 2 2 3 3 4 4 5 5 6 6 7 7 Impossible! 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 Impossible! 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 Impossible! ...
result:
ok 1839 cases