Timus 1642. 1D Maze迷宫

1D people lived in a 1D country. Everything in the country was one-dimensional, and everything was simple and clear: just one axis and two directions — forward and backward. Even a 1D world has problems, though; for instance, finding an exit from a maze. An idea of a 1D maze might seem weird to us, but not to 1D people. Escaping from such a maze is a hard and vital task for them. They solve this task in a following way.

A 1D person chooses a direction: backward (decreasing his coordinate) or forward (increasing it), and then moves in this direction. If he finds an exit, he escapes the maze immediately; if he encounters an obstacle, he reverses his direction and continues walking.

In order to feel the hard life of 1D residents, try to implement a function that will compute a distance a 1D person will walk before finding an exit, based on the initial direction.

Input

The first line contains space-separated integersnandx— the number of obstacles and the coordinate of an exit point<nobr>(0 ≤<em>n</em>≤ 100)</nobr>. 1D person is located at the origin. The second line containsndifferent integers— the coordinates of the obstacles. Each coordinate, includingx, is non-zero and doesn't exceed 1000 in absolute value. No obstacle is located at the exit point. It is guaranteed that 1D person will encounter either obstacle or exit point sooner or later regardless of the initial direction.

Output

Output two space-separated integers — the distance a 1D person should walk before finding an exit if his initial direction is forward or backward, respectively. If he can't find the exit due to the obstacles, output “Impossible”.

Samples

input output

3 -2 -10 -4 2	6 2
3 -2 10 -1 2	Impossible

分好情况就能解决的问题。这里使用了数组，不过好像不需要使用数组，只需要记录靠零点最近的正负点就可以了。

需要细心的题目吧。

#include <vector>
#include <iostream>
using namespace std;

void oneDMaze1642()
{
	int n = 0, x = 0, a = 0;
	cin>>n>>x;
	vector<int> positive;
	vector<int> negative;
	for (int i = 0; i < n; i++)
	{
		cin>>a;
		if (a < 0) negative.push_back(a);
		else positive.push_back(a);
	}
	sort(positive.begin(), positive.end());
	sort(negative.begin(), negative.end());
	if ( positive.size() && positive[0] < x || 
		negative.size() && negative.back() > x) cout<<"Impossible";
	else if (x > 0)
	{
		cout<<x<<' ';
		if (negative.empty()) cout<<"Impossible";
		else cout<<x - 2*negative.back();
	}
	else
	{
		if (positive.empty()) cout<<"Impossible ";
		else cout<<2*positive[0] - x<<' ';
		cout<<-x;
	}
}