레이스
시간 제한2초메모리 제한512 MB
길이 N인 트랙의 K개 후보 지점 중 M개를 골라 심판 간 최소 거리를 이분 탐색으로 최대화한 뒤, 그중 사전식으로 가장 큰 배치를 출력합니다.
문제
길이가 N인 직선 레이스 트랙이 있다.
심판 M명을 트랙 위에 배치하려고 한다. 심판은 아무 위치에나 둘 수 없고, 미리 정해진 K개의 후보 위치 중에서만 배치할 수 있다.
배치한 심판들 중 서로 가장 가까운 두 심판 사이의 거리가 최대가 되도록 심판을 배치해야 한다. 어떤 후보 위치에 심판을 둘지 구하시오.
입력
첫째 줄에 N, M, K가 주어진다.
N은1,000,000이하인 자연수이다.M은K이하인 자연수이다.K는2이상50이하이다.
둘째 줄에는 심판을 둘 수 있는 K개의 위치가 오름차순으로 주어진다. 각 위치는 0이거나 N 이하인 자연수이다.
출력
첫째 줄에 길이가 K인 이진 문자열을 출력한다. i번째 문자는 i번째 후보 위치에 심판을 세우면 1, 세우지 않으면 0이어야 한다.
가장 가까운 두 심판 사이의 거리를 최대로 만드는 배치가 여러 개라면, 사전순으로 가장 늦은 이진 문자열을 출력한다.