首页 > 代码库 > CF 479D Long Jumps

CF 479D Long Jumps


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int a[100010];
int n;

bool find(int x)
{
	int l = 0, r = n-1;
	while(l <= r)
	{
		int m = (l+r) >> 1;
		if(a[m] == x)
			return true; 
		if(a[m] < x)
			l = m+1;
		else
			r = m-1;
	}
	return false;
}
int ok(int x)
{
	for(int i = 0; i < n; i++)
	{
		if(a[i] >= x)
		{
			if(find(a[i]-x))
				return i;
		}
	}
	return -1;
}

bool ok2()
{
	
}
int main()
{
	int l, x, y;
	while(scanf("%d %d %d %d", &n, &l, &x, &y) != EOF)
 	{
 		int f1 = -1, f2 = -1;
		for(int i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
		}
		f1 = ok(x);
		f2 = ok(y);
		if(f1 != -1 && f2 != -1)
		{
			printf("0\n");
			continue;
		}
		if(f1 != -1 && f2 == -1)
		{
			printf("1\n");
			printf("%d\n", y);
		}
		else if(f1 == -1 && f2 != -1)
		{
			printf("1\n");
			printf("%d\n", x);
		}
		else
		{
			int tmp1 = -1, tmp2 = -1;
			for(int i = 0; i < n; i++)
			{
				int s = a[i]-x;
				int e = a[i]+x;
				if(s >= 0 && s <= l && find(s+y))
				{	
					tmp1 = i;
					break;
				}
				if(s >= 0 && s <= l && find(s-y))
				{	
					tmp1 = i;
					break;
				}
				if(e >= 0 && e <= l && find(e+y))
				{	
					tmp2 = i;
					break;
				}
				if(e >= 0 && e <= l && find(e-y))
				{	
					tmp2 = i;
					break;
				}
			}
			if(tmp1 != -1)
			{
				printf("1\n%d\n", a[tmp1]-x);
			}
			else if(tmp2 != -1)
			{
				printf("1\n%d\n", a[tmp2]+x);
			}
			else
			{
				printf("2\n");
				printf("%d %d\n", x, y);
			}
		}
 	}
	return 0;
}


CF 479D Long Jumps