[분할 정복] 숫자 카드

예제 입력 1

5

6 3 2 10 -10

8

10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

 

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

#include <stdio.h>

constexpr int MAX_COUNT = 500000;

int N, M;
int num[MAX_COUNT];
int tempNum[MAX_COUNT];

void mergeSort(int data[], int start, int end)
{
	if (start >= end) return;
	int mid = (start + end) / 2;

	mergeSort(data, start, mid);
	mergeSort(data, mid + 1, end);

	int i = start;
	int j = mid + 1;
	int k = 0;

	while (i <= mid && j <= end)
	{
		if (data[i] <= data[j])
		{
			tempNum[k++] = data[i];
			i++;
		}
		else
		{
			tempNum[k++] = data[j];
			j++;
		}
	}

	while (i <= mid)
	{
		tempNum[k++] = data[i];
		i++;
	}

	while (j <= end)
	{
		tempNum[k++] = data[j];
		j++;
	}

	for (int i = start; i <= end; i++)
		data[i] = tempNum[i - start];
}

int main(void)
{
	scanf("%d", &N);

	for (register int i = 0; i < N; i++)
	{
		scanf("%d", &num[i]);
	}

	mergeSort(num, 0, N - 1);

	scanf("%d", &M);

	for (register int i = 0; i < M; i++)
	{
		int input;
		scanf("%d", &input);

		int start = 0;
		int end = N - 1;

		bool ok = false;

		while (start <= end)
		{
			int mid = (start + end) / 2;

			if (num[mid] == input)
			{
				ok = true;
				break;
			}

			if (input < num[mid]) end = mid - 1;
			else if (input > num[mid]) start = mid + 1;
		}

		if (ok) printf("1 ");
		else printf("0 ");
	}

	return 0;
}