ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212803 | #3828. B | eam2539 | 70 | 1783ms | 7728kb | C++11 | 1.9kb | 2024-10-20 11:31:50 | 2024-10-20 14:39:00 |
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T--)
{
int n, m;
cin >> n >> m;
int total = n * m;
vector < pair < int, int >>pos(total);
vector < vector < int >>grid(n, vector < int >(m));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> grid[i][j];
pos[grid[i][j]] =
{
i, j};
}
}
vector < int >dp(total, 1);
vector < int >prev(total, -1);
int dirs[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
for (int a = 0; a < total; a++)
{
int x = pos[a].first;
int y = pos[a].second;
for (int d = 0; d < 4; d++)
{
int nx = x + dirs[d][0];
int ny = y + dirs[d][1];
if (nx >= 0 && nx < n && ny >= 0 && ny < m)
{
int b = grid[nx][ny];
if (b < a)
{
if (dp[b] + 1 > dp[a])
{
dp[a] = dp[b] + 1;
prev[a] = b;
}
else if (dp[b] + 1 == dp[a])
{
if (prev[a] == -1 || b < prev[a])
{
prev[a] = b;
}
}
}
}
}
}
int max_len = 0;
for (int a = 0; a < total; a++)
{
if (dp[a] > max_len)
{
max_len = dp[a];
}
}
vector < int >candidates;
for (int a = 0; a < total; a++)
{
if (dp[a] == max_len)
{
candidates.push_back(a);
}
}
vector < int >best_path;
for (auto a:candidates)
{
vector < int >path;
int current = a;
while (current != -1)
{
path.push_back(current);
current = prev[current];
}
reverse(path.begin(), path.end());
if (best_path.empty() || path < best_path)
{
best_path = path;
}
}
cout << best_path.size() << "\n";
for (int i = 0; i < best_path.size(); i++)
cout << best_path[i] << (i < best_path.size() - 1 ? " " : "\n");
}
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1272kb
input:
10 3 3 0 1 2 3 4 5 6 7 8 3 3 0 1 2 3 4 5 6 8 7 3 3 0 1 2 3 4 5 7 6 8 3 3 0 1 2 3 4 5 7 8 6 3 3 0 1 2...
output:
5 0 1 2 5 8 6 0 1 2 5 7 8 5 0 1 2 5 8 6 0 1 2 5 6 8 5 0 1 2 5 7 7 0 1 2 5 6 7 8 5 0 1 2 6 8 6 0 1 2 ...
result:
wrong answer 57th numbers differ - expected: '2', found: '4'
Subtask #2:
score: 20
Accepted
Test #3:
score: 20
Accepted
time: 2ms
memory: 1308kb
input:
10 22 45 0 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...
output:
990 0 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 3...
result:
ok 5011 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 1308kb
input:
10 17 58 655 668 708 805 640 926 52 16 9 662 765 129 949 348 678 235 18 464 819 450 211 968 724 754 ...
output:
10 11 42 106 223 265 421 903 923 971 982 10 227 258 271 479 499 509 574 578 580 918 8 1 230 308 441 ...
result:
ok 2052 numbers
Subtask #3:
score: 10
Accepted
Test #5:
score: 10
Accepted
time: 297ms
memory: 7728kb
input:
10 2 100000 143604 106821 145034 44402 118718 156663 77133 28800 81890 12336 191537 118894 103331 75...
output:
13 11306 16007 49522 70570 76999 90088 97453 105217 116458 118241 145649 165150 168193 9 9688 35806 ...
result:
ok 600082 numbers
Subtask #4:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 277ms
memory: 7724kb
input:
10 1 200000 0 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...
output:
200000 0 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 3...
result:
wrong answer 200027th numbers differ - expected: '9894', found: '20165'
Subtask #5:
score: 40
Accepted
Test #7:
score: 40
Accepted
time: 307ms
memory: 6936kb
input:
10 145 1379 140324 86968 96426 123781 39754 103720 60835 118904 114639 53717 27146 110309 39232 5608...
output:
14 8850 11113 25989 34151 36456 84869 93686 115053 144522 160408 175609 177211 186680 198340 14 7010...
result:
ok 799431 numbers
Test #8:
score: 0
Accepted
time: 289ms
memory: 6932kb
input:
10 137 1459 0 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...
output:
199883 0 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 3...
result:
ok 599839 numbers
Test #9:
score: 0
Accepted
time: 310ms
memory: 6928kb
input:
10 431 464 73283 114291 153291 121544 122062 142417 169824 87437 63383 123169 5578 161240 12296 2810...
output:
13 8693 46170 58031 84535 85037 98585 107097 109913 125647 135974 173048 173291 193164 16 5468 18508...
result:
ok 400038 numbers
Test #10:
score: 0
Accepted
time: 299ms
memory: 6936kb
input:
10 287 696 42594 17204 186134 183377 153412 122746 42424 4738 107615 187084 183594 161385 57847 9481...
output:
14 136 58739 82533 100919 115173 123428 128558 129415 134074 151802 155712 174974 184151 184213 14 3...
result:
ok 599743 numbers