QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#242876#7740. Puzzle: Question Markbrothernumb2002WA 253ms6620kbC++207.6kb2023-11-07 17:59:202023-11-07 17:59:20

Judging History

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

  • [2023-11-07 17:59:20]
  • 评测
  • 测评结果：WA
  • 用时：253ms
  • 内存：6620kb
查看
  • [2023-11-07 17:59:20]
  • 提交

answer

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a, i##_ = b; i < i##_; ++i)

using namespace std;
using ll = int64_t;
const int N = 2e3 + 5;
const pair<int, int> S[][4] = {
    {{0, 0}, {0, 1}, {1, 1}, {2, 0}},   {{0, 0}, {0, 2}, {1, 1}, {1, 2}},
    {{0, 0}, {1, -1}, {2, -1}, {2, 0}}, {{0, 0}, {0, 1}, {1, 0}, {1, 2}},
    {{0, 0}, {0, 1}, {1, 0}, {2, 1}},   {{0, 0}, {0, 1}, {1, -1}, {1, 1}},
    {{0, 0}, {1, 1}, {2, 0}, {2, 1}},   {{0, 0}, {0, 2}, {1, 0}, {1, 1}}};
const pair<int, int> T[][8] = {
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 0}, {2, 1}, {3, 0}, {3, 1}},
    {{0, 0}, {0, 1}, {0, 2}, {0, 3}, {1, 0}, {1, 1}, {1, 2}, {1, 3}},
    {{0, 0}, {0, 1}, {1, -1}, {1, 0}, {1, 1}, {2, -1}, {2, 0}, {2, 1}},
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}},
    {{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}},
    {{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 1}, {2, 2}},
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}},
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, -1}, {2, 0}, {3, -1}, {3, 0}},
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {1, -2}, {1, -1}, {2, -2}, {2, -1}},
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 1}, {2, 2}, {3, 1}, {3, 2}},
};
const array<int, 4> Sub[] = {
    // Sub[i] = {u, v, x, y}, T[i] = S[u] + Move(S[v], x, y)
    {0, 6, 1, 0}, {3, 5, 0, 2},
    {4, 7, 1, -1}, {4, 5, 1, 1},  {1, 2, 0, 1}, {7, 6, 0, 1},
    {3, 1, 1, 1}, {0, 2, 1, 0},  {5, 7, 0, -2}, {4, 6, 1, 1},
};
int n, m, b[N][N];
void print() {
    printf("%d\n", m);
    rep(i, 0, n) rep(j, 0, n) printf("%d%c", b[i][j], " \n"[j == n - 1]);
}
namespace BF {
int ans, a[N][N];
void dfsT(int x, int y, int c) {
    if (c + (n - x) * n <= ans)
        return;
    if (x == n) {
        if (c >= ans) {
            ans = c;
            rep(i, 0, n) rep(j, 0, n) b[i][j] = a[i][j];
        }
        return;
    }
    if (y == n)
        return dfsT(x + 1, 0, c);
    if (a[x][y])
        return dfsT(x, y + 1, c);
    dfsT(x, y + 1, c);
    rep(k, 0, 10) {
        int ok = 1;
        rep(i, 0, 8) {
            int u = x + T[k][i].first, v = y + T[k][i].second;
            if (u < 0 || n <= u || v < 0 || n <= v || a[u][v]) {
                ok = 0;
                break;
            }
        }
        if (!ok)
            continue;
        m++;
        rep(i, 0, 8) a[x + T[k][i].first][y + T[k][i].second] = m;
        dfsT(x, y + 1, c + 8);
        rep(i, 0, 8) a[x + T[k][i].first][y + T[k][i].second] = 0;
        m--;
    }
}
void dfsS(int x, int y, int c) {
    if (c + (n - x) * n <= ans)
        return;
    if (x == n) {
        if (c >= ans) {
            ans = c;
            rep(i, 0, n) rep(j, 0, n) b[i][j] = a[i][j];
        }
        return;
    }
    if (y == n)
        return dfsS(x + 1, 0, c);
    if (a[x][y])
        return dfsS(x, y + 1, c);
    dfsS(x, y + 1, c);
    rep(k, 0, 8) {
        int ok = 1;
        rep(i, 0, 4) {
            int u = x + S[k][i].first, v = y + S[k][i].second;
            if (u < 0 || n <= u || v < 0 || n <= v || a[u][v]) {
                ok = 0;
                break;
            }
        }
        if (!ok)
            continue;
        m++;
        rep(i, 0, 4) a[x + S[k][i].first][y + S[k][i].second] = m;
        dfsS(x, y + 1, c + 4);
        rep(i, 0, 4) a[x + S[k][i].first][y + S[k][i].second] = 0;
        m--;
    }
}
void Solve() {
    // scanf("%d", &n);
    { // calc 5
        n = 5;
        dfsS(0, 0, 0);
        print();
    }
    {
        n = 6;
        dfsS(0, 0, 0);
        print();
        dfsT(0, 0, 0);
        print();
    }
    { // calc 9
        n = 9;
        ans = n * n - 5;
        dfsT(0, 0, 0);
        print();
    }
    // { // calc 10
    //     n = 10;
    //     ans = n * n - 5;
    //     dfsT(0, 0, 0);
    //     print();
    // }
    { // calc 13
        n = 13;
        ans = n * n - 1;
        rep(i, 2, 11) rep(j, 0, 9) a[i][j] = -1;
        dfsT(0, 0, 81);
        print();
    }
}
} // namespace BF
/*
 * 4k   -> 0
 * 4k+2 -> 4
 * 4k+1 -> 1
 * 4k+3 -> f(4k+1) -> 1
 * 4k+5 -> f(4k+1) -> 1
 *
 * 3 -> 1
 * 5 -> 5
 * 7 -> 5
 * 9 -> 1
 * 6  -> 4
 * 10 -> 4
 *
 * ans5:
 * 0  0  0  1  1
 * 2  2  3  3  1
 * 0  2  3  1  3
 * 2  4  4  5  5
 * 0  4  5  4  5
 *
 * ans9:
 * 0  1  1  2  2  2  3  3  3
 * 1  1  1  2  2  2  3  3  3
 * 1  1  1  2  2  4  4  3  3
 * 5  5  5  6  6  4  4  4  4
 * 5  5  5  6  6  7  7  4  4
 * 5  5  6  6  7  7  7  8  8
 * 9  9  6  6  7  7  7  8  8
 * 9  9  9 10 10 10 10  8  8
 * 9  9  9 10 10 10 10  8  8
 *
 * ans13:
 * 1  1  1  1  2  2  2  2  3  3  3  4  4
 * 1  1  1  1  2  2  2  2  3  3  3  4  4
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  3  3  4  4
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  5  5  4  4
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  5  5  6  6
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  5  5  6  6
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  5  5  6  6
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  7  7  6  6
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  7  7  7  7
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  8  8  7  7
 *-1 -1 -1 -1 -1 -1 -1 -1 -1  8  8  9  9
 *10 10 10 10 11 11 11 11  8  8  9  9  9
 *10 10 10 10 11 11 11 11  8  8  9  9  9
 */

const int ans5[][5] = {
    {0, 0, 0, 1, 1},
    {2, 2, 3, 3, 1},
    {0, 2, 3, 1, 3},
    {2, 4, 4, 5, 5},
    {0, 4, 5, 4, 5},
}, ans9[][9] = {
    { 0,  1,  1,  2, 12, 12,  3, 13,  3},
    {11,  1, 11, 12,  2, 12,  3,  3, 13},
    {11, 11,  1,  2,  2,  4,  4, 13, 13},
    { 5, 15,  5,  6,  6,  4, 14,  4, 14},
    {15,  5,  5, 16,  6,  7,  7, 14, 14},
    {15, 15, 16,  6, 17,  7, 17,  8,  8},
    { 9,  9, 16, 16, 17, 17,  7,  8, 18},
    {19,  9, 19, 10, 20, 10, 20, 18,  8},
    { 9, 19, 19, 10, 10, 20, 20, 18, 18},
};
void fillS(int x, int y, int k) {
    ++m;
    rep(i, 0, 4) b[x + S[k][i].first][y + S[k][i].second] = m;
}
void fillT(int x, int y, int k) {
    auto [u, v, dx, dy] = Sub[k];
    fillS(x, y, u), fillS(x + dx, y + dy, v);
}
void Solve() {
    scanf("%d", &n);
    m = 0;
    switch (n % 4) {
    case 0:
        for (int i = 0; i < n; i += 2)
            for (int j = 0; j < n; j += 4)
                fillT(i, j, 1);
        print();
        break;
    case 2:
        for (int i = 0; i < n; i += 2)
            for (int j = 0; j < n - 2; j += 4)
                fillT(i, j, 1);
        for (int i = 0, j = n - 2; i < n - 2; i += 4)
            fillT(i, j, 0);
        print();
        break;
    case 1: case 3:
        if (n == 1) print();
        else if (n == 3) fillT(0, 0, 3), print();
        else if (n == 5 || n == 7) {
            m = 5;
            rep(i, 0, 5) rep(j, 0, 5) b[i][j] = ans5[i][j];
            if (n == 7) fillT(0, 5, 0), fillT(5, 0, 1), fillT(4, 5, 2);
            print();
        }
        if (n < 9) break;
        int k = n % 4 - 1;
        n -= k, m = 20;
        int t = (n - 9) / 2;
        rep(i, 0, 9) rep(j, 0, 9)
            b[t + i][j] = ans9[i][j];
        for (int i = t - 2, r = t + 9; i >= 0; i -= 2, r += 2) {
            int cnt = (t - i) / 2 + 1;
            rep(j, 0, cnt) fillT(i, j * 4, 1), fillT(r, j * 4, 1);
            int j = cnt * 4;
            fillT(i, j, 5), fillT(r - 2, j + 1, 7), fillT(r - 1, j + 3, 2), fillT(r - 4, j + 1, 6);
            rep(k, 0, cnt - 1) fillT(i + 3 + 4 * k, j + 1, 0);
            rep(k, 0, cnt) fillT(i + 4 * k, j + 3, 0);
        }
        if (k) {
            fillT(n - 1, n, 2);
            for (int i = 0; i < n - 1; i += 4) fillT(i, n, 0), fillT(n, i, 1);
            n += k;
        }
        print();
        break;
    }
}
int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) Solve();
    return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 5940kb

input:

2
3
4

output:

2
1 1 0
1 2 2
2 1 2
4
1 1 2 2
1 2 1 2
3 3 4 4
3 4 3 4

result:

ok Correct. (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 253ms
memory: 6620kb

input:

246
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
...

output:

0
0
0
0 0
0 0
2
1 1 0
1 2 2
2 1 2
4
1 1 2 2
1 2 1 2
3 3 4 4
3 4 3 4
5
0 0 0 1 1
2 2 3 3 1
0 2 3 1 3
2 4 4 5 5
0 4 5 4 5
8
1 1 2 2 7 7
1 2 1 2 8 7
3 3 4 4 7 8
3 4 3 4 8 8
5 5 6 6 5 0
5 6 5 6 0 0
11
0 0 0 1 1 6 6
2 2 3 3 1 7 6
0 2 3 1 3 6 7
2 4 4 5 5 7 7
0 4 5 4 5 10 10
8 8 9 9 11 10 11
8 9 8 9 11 11 ...

result:

wrong answer Participant's solution is incorrect. The size of 5-th piece != 4. (test case 6)
English 繁體中文 简体中文

伺服器時間: 2024-12-03 04:10:44 | 開源專案