UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212803#3828. Beam2539701783ms7728kbC++111.9kb2024-10-20 11:31:502024-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