480B


  Posted on 01 Dec 2014
binary search

Tutorial


Function “find” in STL set and map can be used to find a element in them in . It made them can be used as a hashtable whose query complexity is instead of .

Solution


#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX_N 100005

int n, mark_len, girl, boy;
int mark[MAX_N];

void input()
{
	scanf("%d%d%d%d", &n, &mark_len, &girl, &boy);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &mark[i]);
	}
}

bool find(int a)
{
	int* p = lower_bound(mark, mark + n, a);
	if (p == mark + n)
		return false;
	return a == *p;
}

void work()
{
	bool found_boy = false;
	bool found_girl = false;
	for (int i = 0; i < n; i++)
	{
		found_boy = found_boy || find(mark[i] + boy);
		found_girl = found_girl || find(mark[i] + girl);
	}
	if (found_boy && found_girl)
	{
		puts("0");
		return;
	}
	if (found_boy)
	{
		puts("1");
		printf("%d\n", girl);
		return;
	}
	if (found_girl)
	{
		puts("1");
		printf("%d\n", boy);
		return;
	}
	for (int i = 0; i < n; i++)
	{
		if ((find(mark[i] + girl - boy) && mark[i] + girl <= mark_len) || find(mark[i] + girl + boy))
		{
			printf("1\n%d\n", mark[i] + girl);
			return;
		}
		if (find(mark[i] - girl + boy) && mark[i] - girl >= 0)
		{
			printf("1\n%d\n", mark[i] - girl);
			return;
		}
	}
	printf("2\n%d %d\n", girl, boy);
}

int main()
{
	input();
	work();
	return 0;
}