QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #253776 | #7740. Puzzle: Question Mark | ucup-team902# | AC ✓ | 227ms | 19388kb | C++17 | 5.2kb | 2023-11-17 15:10:22 | 2023-11-17 15:10:23 |
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][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;
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3652kb
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: 0
Accepted
time: 188ms
memory: 6712kb
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:
ok Correct. (246 test cases)
Test #3:
score: 0
Accepted
time: 205ms
memory: 6116kb
input:
64 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
output:
15252 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...
result:
ok Correct. (64 test cases)
Test #4:
score: 0
Accepted
time: 216ms
memory: 6980kb
input:
45 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355
output:
24180 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...
result:
ok Correct. (45 test cases)
Test #5:
score: 0
Accepted
time: 207ms
memory: 7212kb
input:
35 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390
output:
31684 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...
result:
ok Correct. (35 test cases)
Test #6:
score: 0
Accepted
time: 205ms
memory: 6728kb
input:
30 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420
output:
38220 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 ...
result:
ok Correct. (30 test cases)
Test #7:
score: 0
Accepted
time: 224ms
memory: 19388kb
input:
2 2000 1000
output:
1000000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 5...
result:
ok Correct. (2 test cases)
Test #8:
score: 0
Accepted
time: 217ms
memory: 19288kb
input:
2 1999 999
output:
999000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Test #9:
score: 0
Accepted
time: 212ms
memory: 19276kb
input:
2 1998 998
output:
998000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Test #10:
score: 0
Accepted
time: 207ms
memory: 19364kb
input:
2 1997 997
output:
997002 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Test #11:
score: 0
Accepted
time: 211ms
memory: 19196kb
input:
2 1996 996
output:
996004 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Test #12:
score: 0
Accepted
time: 209ms
memory: 19260kb
input:
2 1995 995
output:
995006 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Test #13:
score: 0
Accepted
time: 221ms
memory: 19256kb
input:
2 1994 994
output:
994008 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Test #14:
score: 0
Accepted
time: 227ms
memory: 19252kb
input:
2 1993 993
output:
993012 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Test #15:
score: 0
Accepted
time: 198ms
memory: 19168kb
input:
2 1992 992
output:
992016 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Test #16:
score: 0
Accepted
time: 199ms
memory: 19240kb
input:
2 1991 991
output:
991020 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52...
result:
ok Correct. (2 test cases)
Extra Test:
score: 0
Extra Test Passed