QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#184198#6791. Domino Tilingucup-team004#AC ✓18ms3668kbC++204.9kb2023-09-20 15:01:152023-09-20 15:01:16

Judging History

你现在查看的是最新测评结果

  • [2023-09-20 15:01:16]
  • 评测
  • 测评结果:AC
  • 用时:18ms
  • 内存:3668kb
  • [2023-09-20 15:01:15]
  • 提交

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