QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #242876 | #7740. Puzzle: Question Mark | brothernumb2002 | WA | 253ms | 6620kb | C++20 | 7.6kb | 2023-11-07 17:59:20 | 2023-11-07 17:59:20 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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)