QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #736975 | #5135. Kiosk Construction | awesomemaths | AC ✓ | 4632ms | 3720kb | C++14 | 2.4kb | 2024-11-12 14:08:10 | 2024-11-12 14:08:10 |
Judging History
answer
using namespace std;
#include <bits/stdc++.h>
#define ll int
#define MAXN 45
ll store[MAXN][MAXN], h, w;
ll dfs(ll i, ll j, ll fi, ll fj, vector<ll> &visited, ll track)
{
if(visited[store[i][j]] == 1){
return -1;
}
visited[store[i][j]] = 1;
if(i == fi && j == fj){
return track;
}
ll dest = store[fi][fj];
ll curr = store[i][j];
ll curr1 = 1e9;
ll curr2 = 1e9;
ll cx = 0; ll cy = 0;
for(int x = -1; x <= 1; x+=2){
if(i + x >= 1 && i + x <= h){
if((abs(dest - store[i + x][j]) < curr1) || (abs(dest - store[i + x][j]) == curr1 && abs(curr - store[i + x][j]) < curr2)){
cx = i + x; cy = j;
curr1 = abs(dest - store[i + x][j]);
curr2 = abs(curr - store[i + x][j]);
}
}
}
for(int y = -1; y <= 1; y+=2){
if(j + y >= 1 && j + y <= w){
if((abs(dest - store[i][j + y]) < curr1) || (abs(dest - store[i][j + y]) == curr1 && abs(curr - store[i][j + y]) < curr2)){
cx = i; cy = j + y;
curr1 = abs(dest - store[i][j + y]);
curr2 = abs(curr - store[i][j + y]);
}
}
}
return dfs(cx, cy, fi, fj, visited, track + 1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> h >> w;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
cin >> store[i][j];
}
}
ll o_res = 1e9;
ll res1 = -1;
for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++){
ll cnt = 0;
bool flag = true;
ll res = 0;
for(int i1 = 1; i1 <= h; i1++){
for(int j1 = 1; j1 <= w; j1++){
vector<ll> visited(h * w + 1);
ll get = dfs(i, j, i1, j1, visited, 0);
res = max(res, get);
if(get == -1){
flag = false;
break;
}
}
if(!flag) break;
}
if(flag){
if(res < o_res){
o_res = res;
res1 = store[i][j];
}
}
}
}
if(o_res == 1e9){
cout << "impossible\n";
}
else{
cout << res1 << " " << o_res << "\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3708kb
input:
2 3 1 2 3 6 5 4
output:
2 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
3 3 1 4 8 7 5 2 3 9 6
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
3 3 9 3 1 4 7 2 8 6 5
output:
4 3
result:
ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
2 2 1 2 3 4
output:
1 2
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 2 4 3 1 2
output:
4 2
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
2 3 3 5 2 6 1 4
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
2 3 5 3 4 1 6 2
output:
6 2
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
3 2 2 4 6 3 1 5
output:
6 2
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 3 1 5 9 7 2 8 6 4 3
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
3 3 8 3 9 5 6 2 1 4 7
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
5 3 4 12 8 7 6 10 2 1 13 3 9 14 5 11 15
output:
impossible
result:
ok
Test #12:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 5 24 23 3 10 1 6 7 9 18 5 25 2 20 11 8 4 13 12 14 15 17 21 22 19 16
output:
impossible
result:
ok
Test #13:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
10 10 83 24 7 98 40 18 56 81 12 73 77 87 33 22 61 38 8 48 63 34 25 29 72 97 28 26 54 3 89 13 65 60 42 45 55 36 16 70 17 5 90 69 74 64 99 31 9 2 66 51 44 35 14 58 71 27 92 84 32 100 6 82 37 76 52 43 39 59 91 41 50 11 15 85 62 10 20 86 53 95 46 68 4 49 1 75 93 19 23 57 80 96 78 67 79 30 88 47 94 21
output:
impossible
result:
ok
Test #14:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
20 10 86 175 137 160 149 72 135 64 2 131 134 83 66 148 141 1 171 90 178 57 108 152 179 136 47 67 142 124 121 59 146 41 126 89 114 118 196 112 125 19 26 180 50 107 96 188 128 14 94 88 156 7 49 76 91 117 56 104 161 127 105 195 184 40 24 139 3 190 106 80 116 21 34 12 87 97 130 140 103 98 192 81 157 194...
output:
impossible
result:
ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
2 40 59 36 73 43 16 15 2 49 51 21 30 79 60 78 48 19 4 45 77 65 3 63 22 11 57 58 54 76 27 70 25 12 62 69 29 1 50 35 14 17 71 56 13 66 75 26 6 68 37 72 46 38 53 8 41 24 32 31 33 80 23 64 5 52 20 9 40 61 34 10 39 47 67 74 42 18 7 55 28 44
output:
impossible
result:
ok
Test #16:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
40 40 1545 1478 236 1013 790 988 319 1231 822 1598 1505 529 340 1441 224 681 1449 537 151 1087 966 552 938 101 676 136 807 1507 1079 328 1200 34 645 1127 316 518 357 726 121 1314 971 1266 564 954 468 627 1198 208 799 793 956 1206 70 343 406 221 142 408 1131 1533 504 1279 764 629 498 455 366 1407 991...
output:
impossible
result:
ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 3716kb
input:
40 40 1559 1253 109 396 934 203 833 1534 130 603 105 395 384 1521 713 647 1170 379 392 269 67 919 1447 429 784 688 106 885 763 853 621 680 1098 120 1486 1101 1099 852 748 1395 472 327 932 977 1451 65 670 460 673 838 1106 236 649 164 1407 1439 1068 1037 315 1326 70 143 474 1556 740 1390 237 938 1310 ...
output:
impossible
result:
ok
Test #18:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 3 1 2 3 4 5 6 7 8 9
output:
1 4
result:
ok
Test #19:
score: 0
Accepted
time: 14ms
memory: 3596kb
input:
40 31 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 10...
output:
15 55
result:
ok
Test #20:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
3 40 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:
20 22
result:
ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
40 3 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:
1 41
result:
ok
Test #22:
score: 0
Accepted
time: 21ms
memory: 3660kb
input:
40 40 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 10...
output:
20 59
result:
ok
Test #23:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
3 3 1 2 3 6 5 4 7 8 9
output:
5 2
result:
ok
Test #24:
score: 0
Accepted
time: 101ms
memory: 3588kb
input:
27 27 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 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 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 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 ...
output:
365 26
result:
ok
Test #25:
score: 0
Accepted
time: 5ms
memory: 3632kb
input:
21 10 1 2 3 4 5 6 7 8 9 10 20 19 18 17 16 15 14 13 12 11 21 22 23 24 25 26 27 28 29 30 40 39 38 37 36 35 34 33 32 31 41 42 43 44 45 46 47 48 49 50 60 59 58 57 56 55 54 53 52 51 61 62 63 64 65 66 67 68 69 70 80 79 78 77 76 75 74 73 72 71 81 82 83 84 85 86 87 88 89 90 100 99 98 97 96 95 94 93 92 91 10...
output:
105 15
result:
ok
Test #26:
score: 0
Accepted
time: 147ms
memory: 3596kb
input:
40 21 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
output:
410 30
result:
ok
Test #27:
score: 0
Accepted
time: 591ms
memory: 3716kb
input:
39 39 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 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
output:
761 38
result:
ok
Test #28:
score: 0
Accepted
time: 676ms
memory: 3600kb
input:
40 40 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 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...
output:
781 40
result:
ok
Test #29:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
11 11 1 102 103 104 105 106 107 108 109 110 111 2 101 36 35 34 33 32 31 30 29 112 3 100 37 74 75 76 77 78 79 28 113 4 99 38 73 56 55 54 53 80 27 114 5 98 39 72 57 62 63 52 81 26 115 6 97 40 71 58 61 64 51 82 25 116 7 96 41 70 59 60 65 50 83 24 117 8 95 42 69 68 67 66 49 84 23 118 9 94 43 44 45 46 47...
output:
28 27
result:
ok
Test #30:
score: 0
Accepted
time: 3993ms
memory: 3660kb
input:
39 39 1 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 2 1445 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125...
output:
368 367
result:
ok
Test #31:
score: 0
Accepted
time: 4632ms
memory: 3720kb
input:
40 40 1 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 2 1522 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 13...
output:
387 386
result:
ok
Test #32:
score: 0
Accepted
time: 1688ms
memory: 3668kb
input:
31 37 1 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 2 1081 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 1...
output:
872 275
result:
ok
Test #33:
score: 0
Accepted
time: 4309ms
memory: 3672kb
input:
40 39 1 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 2 1483 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127...
output:
378 377
result:
ok
Test #34:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
40 40 831 832 833 834 835 851 852 853 854 855 858 859 860 827 826 821 820 880 881 882 788 1486 1487 1488 18 1492 1493 1496 1495 1494 1546 1547 1548 1549 17 16 15 12 11 2 841 840 839 837 836 850 955 954 953 952 857 856 861 862 825 822 878 879 789 883 884 1485 1484 1489 1490 1491 1498 1497 1502 1503 1...
output:
impossible
result:
ok
Test #35:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
40 40 633 634 635 614 639 641 640 645 646 647 648 649 650 651 652 654 655 613 612 609 673 693 692 691 675 676 674 721 722 723 451 450 449 448 445 444 441 440 429 430 632 631 636 637 638 642 643 644 836 835 834 833 832 831 830 653 656 605 611 610 672 694 685 690 689 678 679 720 479 724 334 335 336 44...
output:
impossible
result:
ok
Test #36:
score: 0
Accepted
time: 500ms
memory: 3680kb
input:
30 37 1 2 3 46 47 48 49 52 53 56 57 58 59 62 63 66 67 68 69 70 83 84 85 86 87 90 91 124 125 126 127 168 169 170 171 182 183 18 17 4 45 44 43 50 51 54 55 598 597 60 61 64 65 578 577 72 71 82 81 98 97 88 89 92 123 130 129 128 167 166 165 172 181 184 19 16 5 6 7 42 41 40 601 600 599 596 593 592 591 590...
output:
255 79
result:
ok
Test #37:
score: 0
Accepted
time: 770ms
memory: 3656kb
input:
40 33 1 2 3 6 7 8 9 14 15 18 19 314 315 318 319 322 323 324 325 326 327 336 337 458 459 460 461 476 477 486 487 496 497 98 97 4 5 76 75 10 13 16 17 20 313 316 317 320 321 360 359 330 329 328 335 338 457 456 455 462 475 478 485 488 495 498 99 96 81 80 77 74 11 12 25 24 21 312 371 370 369 368 361 358 ...
output:
1263 71
result:
ok
Test #38:
score: 0
Accepted
time: 1244ms
memory: 3604kb
input:
40 40 1 2 3 6 7 1028 1029 1032 1033 1036 1037 1038 1039 1044 1045 1050 1051 1062 1063 1096 1097 1100 1101 1106 1107 1110 1111 1116 1117 1120 1121 1122 1123 1126 1127 1140 1141 1144 1145 1600 22 21 4 5 8 1027 1030 1031 1034 1035 936 935 1040 1043 1046 1049 1052 1061 1064 1095 1098 1099 1102 1105 1108...
output:
128 77
result:
ok
Test #39:
score: 0
Accepted
time: 1114ms
memory: 3676kb
input:
40 40 1 2 3 24 25 32 33 42 43 710 711 712 713 744 745 746 747 748 749 754 755 756 757 758 759 762 763 770 771 772 1577 1578 1579 1582 1583 1588 1589 1590 1599 1600 8 7 4 23 26 31 34 41 44 709 708 707 714 743 738 737 736 735 750 753 684 683 680 679 760 761 764 769 768 773 1576 1575 1580 1581 1584 158...
output:
1080 74
result:
ok