QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#216707 | #5135. Kiosk Construction | MovingUp# | WA | 64ms | 35432kb | C++14 | 2.6kb | 2023-10-15 21:26:40 | 2023-10-15 21:26:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1005;
const int inf = 1e9;
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};
vector<pair<int,int>> edge[Nmax][Nmax];
int dist[Nmax][Nmax], Dist[Nmax][Nmax];
int a[Nmax][Nmax];
int n, m;
bool ok[Nmax][Nmax];
void dfs(int x, int y)
{
for(auto it : edge[x][y])
{
dist[it.first][it.second] = dist[x][y] + 1;
dfs(it.first, it.second);
}
}
bool valid(int x, int y)
{
return (1<= x && x <= n && 1 <= y && y <= m);
}
void solve(int x, int y)
{
int val = a[x][y];
int i, j, k;
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
{
edge[i][j].clear();
dist[i][j] = -1;
}
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
{
if(i == x && j == y) continue;
int curr_abs = inf, curr_abs2 = inf, pos_i = -1, pos_j = -1;
for(k=0; k<4; ++k)
{
int ii = i + dx[k];
int jj = j + dy[k];
if(valid(ii, jj))
{
if(abs(a[ii][jj] - val) < curr_abs || (abs(a[ii][jj] - val == curr_abs && abs(a[ii][jj] - a[i][j]) < curr_abs2)))
{
curr_abs = abs(a[ii][jj] - val);
curr_abs2 = abs(a[ii][jj] - a[i][j]);
pos_i = ii;
pos_j = jj;
}
}
}
edge[pos_i][pos_j].push_back({i, j});
}
dist[x][y] = 0;
dfs(x, y);
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
{
Dist[i][j] = max(Dist[i][j], dist[i][j]);
ok[i][j] &= (dist[i][j] != -1);
}
}
int main()
{
// freopen("input", "r", stdin);
cin.tie(0); cin.sync_with_stdio(false);
cin >> n >> m;
int i, j;
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
{
cin >> a[i][j];
ok[i][j] = 1;
}
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
solve(i, j);
bool have_answer = 0;
int x, y;
for(i=1; i<=n; ++i)
for(j=1; j<=m; ++j)
if(ok[i][j])
{
if(!have_answer || Dist[i][j] < Dist[x][y])
{
have_answer = 1;
x = i, y = j;
}
}
if(!have_answer)
cout << "impossible\n";
else cout << a[x][y] << ' ' << Dist[x][y] << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 30364kb
input:
2 3 1 2 3 6 5 4
output:
2 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 31652kb
input:
3 3 1 4 8 7 5 2 3 9 6
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 31648kb
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: 29792kb
input:
2 2 1 2 3 4
output:
1 2
result:
ok
Test #5:
score: 0
Accepted
time: 3ms
memory: 33032kb
input:
2 2 4 3 1 2
output:
4 2
result:
ok
Test #6:
score: 0
Accepted
time: 0ms
memory: 30216kb
input:
2 3 3 5 2 6 1 4
output:
impossible
result:
ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 33152kb
input:
2 3 5 3 4 1 6 2
output:
6 2
result:
ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 33004kb
input:
3 2 2 4 6 3 1 5
output:
6 2
result:
ok
Test #9:
score: 0
Accepted
time: 7ms
memory: 31320kb
input:
3 3 1 5 9 7 2 8 6 4 3
output:
impossible
result:
ok
Test #10:
score: 0
Accepted
time: 4ms
memory: 33192kb
input:
3 3 8 3 9 5 6 2 1 4 7
output:
impossible
result:
ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 31360kb
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: 30068kb
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: 2ms
memory: 33216kb
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: 4ms
memory: 30748kb
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: 29860kb
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: 64ms
memory: 33340kb
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: 56ms
memory: 30768kb
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: 30212kb
input:
3 3 1 2 3 4 5 6 7 8 9
output:
1 4
result:
ok
Test #19:
score: 0
Accepted
time: 29ms
memory: 33224kb
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: 4ms
memory: 33068kb
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: 3ms
memory: 30748kb
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: 50ms
memory: 30248kb
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: 31880kb
input:
3 3 1 2 3 6 5 4 7 8 9
output:
5 2
result:
ok
Test #24:
score: 0
Accepted
time: 12ms
memory: 30192kb
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: 9ms
memory: 33472kb
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: 16ms
memory: 31600kb
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: 46ms
memory: 33552kb
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: 48ms
memory: 35432kb
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: -100
Wrong Answer
time: 0ms
memory: 30380kb
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:
27 26
result:
FAIL Reported distance is not correct.