QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #397834 | #5135. Kiosk Construction | ucup-team1001# | AC ✓ | 6337ms | 3852kb | C++23 | 3.2kb | 2024-04-24 17:29:01 | 2024-04-24 17:29:02 |
Judging History
answer
/*
Author: Haze
2024/4/24
*/
#include <bits/stdc++.h>
#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;
inline ll read() {
ll s = 0;
bool fl = false;
char ch = (char) getchar();
while (!isdigit(ch)) {
if (ch == '-')fl = true;
ch = (char) getchar();
}
while (isdigit(ch)) {
s = s * 10 + (ch ^ 48);
ch = (char) getchar();
}
return fl ? -s : s;
}
const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;
int a[44][44];
int usd[41][41];
void solve() {
int n = read(), m = read();
irep(i ,1, n){
irep(j, 1, m){
a[i][j] = read();
}
}
vector<array<int, 2>> d = {
{1, 0},
{-1,0},
{0, 1},
{0, -1}
};
int DANS = mod, NUM = -1;
irep(i, 1, n){
irep(j, 1, m){
int D = -1, ok = 1;
irep(k, 1, n){
irep(l, 1, m){
int num = a[k][l];
//(i, j) -> (k, l)
int x = i, y = j;
memset(usd, -1, sizeof usd);
usd[x][y] = 0;
while(x != k || y != l){
int x1, y1, del = 9980000, curnum = 9980000;
for(auto [dx, dy] : d){
if(x + dx <= n && x + dx >= 1 && y + dy <= m && y + dy >= 1){
if(abs(a[x + dx][y + dy] - num) < del ||
abs(a[x + dx][y + dy] - num) == del && abs(a[x + dx][y + dy] - a[x][y]) < curnum){
curnum = abs(a[x + dx][y + dy] - a[x][y]);
del = abs(a[x + dx][y + dy] - num);
x1 = x + dx, y1 = y + dy;
}
}
}
// cerr << "[]" << x1 << ' ' << y1 << endl;
if(usd[x1][y1] != -1){
ok = 0;
break;
}
usd[x1][y1] = usd[x][y] + 1;
x = x1, y = y1;
}
if(ok == 0)break;
D = max(D, usd[k][l]);
// irep(p,1,n){
// irep(q,1,m)cerr << usd[p][q] << ' ';
// cerr << endl;
// }
// cerr << endl;
}
if(ok == 0)break;
}
if(ok){
if(D < DANS){
DANS = D;
NUM = a[i][j];
}
// DANS =
// cout << a[i][j] << ' ' << D;
// return;
}
}
}
if(NUM == -1)
cout << "impossible";
else cout << NUM << ' ' << DANS;
}
int main() {
// IOS
int T = 1;
while (T--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3492kb
input:
2 3 1 2 3 6 5 4
output:
2 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
3 3 1 4 8 7 5 2 3 9 6
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3604kb
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: 3580kb
input:
2 2 1 2 3 4
output:
1 2
result:
ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
2 2 4 3 1 2
output:
4 2
result:
ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
2 3 3 5 2 6 1 4
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3492kb
input:
2 3 5 3 4 1 6 2
output:
6 2
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
3 2 2 4 6 3 1 5
output:
6 2
result:
ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 3 1 5 9 7 2 8 6 4 3
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
3 3 8 3 9 5 6 2 1 4 7
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 3544kb
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: 3852kb
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: 3520kb
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: 3780kb
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: 3604kb
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: 3620kb
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: 3852kb
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: 1ms
memory: 3612kb
input:
3 3 1 2 3 4 5 6 7 8 9
output:
1 4
result:
ok
Test #19:
score: 0
Accepted
time: 18ms
memory: 3852kb
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: 1ms
memory: 3840kb
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: 3780kb
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: 29ms
memory: 3552kb
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: 1ms
memory: 3608kb
input:
3 3 1 2 3 6 5 4 7 8 9
output:
5 2
result:
ok
Test #24:
score: 0
Accepted
time: 124ms
memory: 3644kb
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: 8ms
memory: 3616kb
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: 174ms
memory: 3652kb
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: 735ms
memory: 3620kb
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: 803ms
memory: 3560kb
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: 4ms
memory: 3596kb
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: 5430ms
memory: 3784kb
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: 6337ms
memory: 3556kb
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: 2320ms
memory: 3620kb
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: 5848ms
memory: 3584kb
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: 3588kb
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: 3528kb
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: 700ms
memory: 3852kb
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: 1015ms
memory: 3628kb
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: 1640ms
memory: 3564kb
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: 1398ms
memory: 3844kb
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