QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #253772 | #7740. Puzzle: Question Mark | ucup-team902# | WA | 194ms | 4628kb | C++17 | 5.2kb | 2023-11-17 14:59:28 | 2023-11-17 14:59:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int mp9[9][9] = {
{ 0, 1, 1, 3, 4, 4, 5, 6, 5 },
{ 2, 1, 2, 4, 3, 4, 5, 5, 6 },
{ 2, 2, 1, 3, 3, 15, 15, 6, 6 },
{ 8, 7, 7, 12, 12, 15, 16, 15, 16 },
{ 7, 8, 7, 11, 12, 13, 13, 16, 16 },
{ 8, 8, 11, 12, 14, 14, 13, 19, 19 },
{ 9, 9, 11, 11, 14, 13, 14, 20, 19 },
{ 10, 9, 10, 17, 17, 18, 18, 19, 20 },
{ 9, 10, 10, 17, 18, 17, 18, 20, 20 }
};
int mp5[5][5] = {
{ 0, 1, 1, 2, 2 },
{ 0, 1, 2, 1, 2 },
{ 5, 0, 0, 3, 3 },
{ 0, 5, 4, 3, 4 },
{ 5, 5, 4, 4, 3 }
};
int ans[2005][2005];
int n;
int tot = 0;
void insert11(int x, int y)
{
tot++;
ans[x][y] = ans[x][y + 1] = ans[x + 1][y] = ans[x + 1][y + 2] = tot;
tot++;
ans[x][y + 2] = ans[x][y + 3] = ans[x + 1][y + 1] = ans[x + 1][y + 3] = tot;
}
void insert12(int x, int y)
{
tot++;
ans[x][y] = ans[x][y + 1] = ans[x + 1][y + 1] = ans[x + 2][y] = tot;
tot++;
ans[x + 3][y] = ans[x + 3][y + 1] = ans[x + 2][y + 1] = ans[x + 1][y] = tot;
}
void insert21(int x, int y)
{
tot++;
ans[x][y] = ans[x + 1][y] = ans[x][y + 1] = ans[x + 1][y + 2] = tot;
tot++;
ans[x][y + 2] = ans[x + 1][y + 1] = ans[x + 2][y + 1] = ans[x + 2][y + 2] = tot;
}
void insert22(int x, int y)
{
tot++;
ans[x][y] = ans[x + 1][y + 1] = ans[x][y + 1] = ans[x + 2][y] = tot;
tot++;
ans[x + 1][y - 1] = ans[x + 2][y - 1] = ans[x + 2][y + 1] = ans[x + 1][y] = tot;
}
void insert31(int x, int y)
{
tot++;
ans[x][y] = ans[x + 1][y] = ans[x + 1][y + 1] = ans[x - 1][y + 1] = tot;
tot++;
ans[x - 2][y + 1] = ans[x - 2][y + 2] = ans[x - 1][y + 2] = ans[x][y + 1] = tot;
}
void insert32(int x, int y)
{
tot++;
ans[x][y] = ans[x + 1][y] = ans[x + 1][y + 1] = ans[x + 1][y + 2] = tot;
tot++;
ans[x + 1][y + 1] = ans[x + 1][y + 3] = ans[x + 2][y + 2] = ans[x + 2][y + 3] = tot;
}
void getans(int x, int y, int sz)
{
if (sz == 9) {
for (int i = 1; i <= sz; ++i)
for (int j = 1; j <= sz; ++j) {
ans[i + x - 1][j + y - 1] = mp9[i - 1][j - 1] == 0 ? 0 : mp9[i - 1][j - 1] + tot;
}
tot += 20;
return;
}
for (int i = 1; i + 3 <= sz - 5; i += 4) {
insert11(x, y + i - 1);
}
insert21(x, y + sz - 5);
insert22(x + sz - 3, y + sz - 2);
for (int i = 1; i + 3 <= sz - 5; i += 4) {
insert11(x + sz - 2, y + i - 1);
}
insert31(x + sz - 2, y + sz - 5);
insert32(x + sz - 6, y + sz - 4);
for (int i = 1; i + 3 <= sz - 5; i += 4) {
insert12(x + i - 1, y + sz - 2);
}
for (int i = 4; i + 3 <= sz - 6; i += 4) {
insert12(x + i - 1, y + sz - 4);
}
getans(x + 2, y, sz - 4);
}
void solve()
{
cin >> n;
tot = 0;
if (n == 1) {
cout << 0 << endl;
cout << 0 << endl;
return;
}
if (n == 2) {
cout << 0 << endl;
cout << "0 0" << endl;
cout << "0 0" << endl;
return;
}
if (n == 3) {
cout << 2 << endl;
cout << "0 1 1" << endl;
cout << "2 2 1" << endl;
cout << "2 1 2" << endl;
return;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
ans[i][j] = 0;
if (n % 4 == 0) {
for (int i = 1; i + 1 <= n; i += 2) {
for (int j = 1; j + 3 <= n; j += 4) {
insert11(i, j);
}
}
}
if (n % 4 == 2) {
for (int i = 1; i + 1 <= n; i += 2) {
for (int j = 1; j + 3 <= n; j += 4) {
insert11(i, j);
}
}
for (int i = 1; i + 3 <= n; i += 4)
insert12(i, n - 1);
}
if (n % 4 == 1) {
if (n == 5) {
tot = 5;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
ans[i][j] = mp5[i - 1][j - 1];
}
}
if (n >= 9) {
getans(1, 1, n);
}
}
if (n % 4 == 3) {
if (n == 7) {
tot = 5;
for (int i = 1; i <= n - 2; ++i)
for (int j = 1; j <= n - 2; ++j) {
ans[i][j] = mp5[i - 1][j - 1];
}
for (int i = 1; i + 3 <= n - 3; ++i) {
insert11(n - 1, i);
}
for (int i = 1; i + 3 <= n - 3; ++i) {
insert12(i, n - 1);
}
insert22(n - 2, n - 1);
}
if (n >= 9) {
getans(1, 1, n - 2);
for (int i = 1; i + 3 <= n - 3; i+=4) {
insert11(n - 1, i);
}
for (int i = 1; i + 3 <= n - 3; i+=4) {
insert12(i, n - 1);
}
insert22(n - 2, n - 1);
}
}
cout << tot << '\n';
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cout << ans[i][j] << " \n"[j == n];
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3400kb
input:
2 3 4
output:
2 0 1 1 2 2 1 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: 194ms
memory: 4628kb
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 0 1 1 2 2 1 2 1 2 4 1 1 2 2 1 2 1 2 3 3 4 4 3 4 3 4 5 0 1 1 2 2 0 1 2 1 2 5 0 0 3 3 0 5 4 3 4 5 5 4 4 3 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 0 0 5 6 5 6 0 0 11 0 1 1 2 2 8 8 0 1 2 1 2 9 8 5 0 0 3 3 8 9 0 5 4 3 4 9 9 5 5 4 4 3 10 10 6 6 7 7 11 11 10 6 7 6 7 11 10 ...
result:
wrong answer Participant's solution is incorrect. The size of 15-th piece != 4. (test case 13)