UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212717#3828. Bxxc093ms6428kbC++2.1kb2024-10-20 09:56:242024-10-20 14:36:45

answer

#include<iostream>
#include<vector>
#include<map>
#include<cstdio>

using namespace std;
vector<vector<long long> > v;
int fx[5]={0,-1,1,0,0},fy[5]={0,0,0,-1,1},n,m;
map<long long,map<long long,vector<long long> > > visited;
vector<long long> ans;
bool check(const vector<long long> x,const vector<long long> y,long long len)
{
	for(int i=0;i<len;i++)
	{
		if(x[i]>y[i])
		{
			return true;
		}
		if(x[i]<y[i])
		{
			return false;
		}
	}
	return false;
}
void f(int x,int y)
{
	
	//cout<<x<<' '<<y<<endl;
	if(x<0||y<0||x>=n||y>=m)
	{
		return;
	}
	if(!visited[x][y].empty())
	{
		return;
	}
	visited[x][y].push_back(v[x][y]);
	for(int i=1;i<=4;i++)
	{
		if((x+fx[i])<n&&(y+fy[i])<m&&(x+fx[i])>=0&&(y+fy[i])>=0&&v[x+fx[i]][y+fy[i]]>v[x][y])
			f(x+fx[i],y+fy[i]);
	}
	int tx=0,ty=0,maxx=0;
	for(int i=1;i<=4;i++)
	{
		if((x+fx[i])<n&&(y+fy[i])<m&&(x+fx[i])>=0&&(y+fy[i])>=0&&v[x+fx[i]][y+fy[i]]>v[x][y])
		{
			int len=visited[x+fx[i]][y+fy[i]].size();
			if(len>maxx)
			{
				maxx=len;
				tx=x+fx[i];
				ty=y+fy[i];
			}
			if(len==maxx)
			{
				if(check(visited[x+fx[i]][y+fy[i]],visited[tx][ty],len))
				{
					ans=visited[x+fx[i]][y+fy[i]];
				}
			}
		}
	}
	for(int i=0;i<maxx;i++)
	{
		visited[x][y].push_back(visited[tx][ty][i]);
	}
	return;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		v.clear();
		visited.clear();
		ans.clear();
		cin>>n>>m;
		for(int i=0;i<n;i++)
		{
			vector<long long> t;
			for(int j=0;j<m;j++)
			{
				long long a;
				cin>>a;
				t.push_back(a);
			}
			v.push_back(t);
		}
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				f(i,j);
			}
		}
		int x,y;
		long long maxx=1;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				long long len=visited[i][j].size();
				if(len>maxx)
				{
					maxx=len;
					x=i,y=j;
					ans=visited[i][j];
				}
				if(len==maxx)
				{
					if(check(visited[i][j],ans,len))
					{
						ans=visited[i][j];
					}
				}
			}
		}
		printf("%lld\n",maxx);
		for(int i=0;i<maxx;i++)
		{
			printf("%lld ",visited[x][y][i]);
		}
		printf("\n");
	}
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1268kb

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 3 6 7 8 
6
0 3 4 5 7 8 
5
0 3 4 6 7 
6
0 3 4 5 6 8 
5
0 3 4 6 8 
7
0 3 4 5 6 7 8 
5
0 3 5 7 8 
6...

result:

wrong answer 3rd numbers differ - expected: '1', found: '3'

Subtask #2:

score: 0
Wrong Answer

Test #3:

score: 0
Wrong Answer
time: 93ms
memory: 6428kb

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:

wrong answer 1000th numbers differ - expected: '462', found: '563'

Subtask #3:

score: 0
Time Limit Exceeded

Test #5:

score: 0
Time Limit Exceeded

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:


Subtask #4:

score: 0
Time Limit Exceeded

Test #6:

score: 0
Time Limit Exceeded

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:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #7:

score: 0
Time Limit Exceeded

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 138729 144522 160408 175609 177211 186680 198340 
14
701...

result: