색상 팔레트

시간 제한3초메모리 제한1024 MB

요약

K비트 색을 삽입하면서, 각 질의 색에 대해 일치하는 비트가 가장 많은 저장된 색을 찾고, 동점이면 가장 작은 값을 반환한다.

난이도: 보통10점 중 7점
유형: 트라이, 비트 연산, 그리디, 완전 탐색
정답자: 아직 제출이 없습니다

문제

그래픽 소프트웨어를 만드는 회사에서 새 그래픽 프로그램을 개발하고 있다. 이 프로그램의 모듈 중 하나는 색상 팔레트를 관리한다. 프로그램이 시작되면 팔레트는 비어 있다. 사용자는 팔레트에 새로운 색을 추가하거나, 주어진 색과 팔레트에 있는 색 중 가장 비슷한 색이 무엇인지 물어볼 수 있다.

색은 $K$ 비트 정수( $0$ 부터 $2^K-1$ 까지의 값)로 표현하며, 두 색의 유사도는 두 색의 비트 표현에서 값이 일치하는 비트의 개수로 정의한다. 예를 들어 $K = 5$ 일 때 색 00110과 10101의 유사도는 $2$ 인데, 왼쪽에서 두 번째와 세 번째 비트만 서로 값이 같기 때문이다.

프로그램은 다음 연산들로 이루어진 색상 팔레트 관리 모듈처럼 동작하며, 각 연산이 호출되는 순서대로 로그를 출력한다.

연산	설명
`init(int k, int n)`	$k$ 비트 색을 사용하도록 팔레트를 초기화한다. 프로그램 시작 시 한 번 호출되며, 그 뒤에 `add`와 `find` 호출이 모두 합쳐 $n$ 번 이어진다.
`add(int c)`	색 $c$ 를 팔레트에 추가한다.
`find(int c)`	색 $c$ 에 대해 팔레트에서 가장 잘 맞는 색을 찾는다. 팔레트의 색 중 $c$ 와의 유사도가 가장 큰 색을 반환한다. 유사도가 가장 큰 색이 여러 개이면 그중 값이 가장 작은 색을 반환한다. 이 연산은 팔레트에 색이 최소 한 개 있을 때만 호출된다.
`done()`	작업 종료. 프로그램 끝에서 한 번 호출된다.

입력

입력의 첫 줄에는 색을 표현하는 데 사용하는 비트 수 $K$ ( $1 \le K \le 20$ )와 연산의 개수 $N$ ( $1 \le N \le 10^6$ )이 주어진다. 이어지는 $N$ 개의 줄에는 각각 두 정수 $T_i$ 와 $C_i$ ( $0 \le C_i < 2^K$ )가 주어진다. $T_i = 1$ 은 색 $C_i$ 를 팔레트에 추가함을, $T_i = 2$ 는 색 $C_i$ 에 대해 팔레트에서 가장 잘 맞는 색을 찾음을 뜻한다.

출력

모듈이 처리한 연산들의 로그를 출력한다. 먼저 init(K, N)을 출력한다. 그다음 각 연산을 주어진 순서대로 처리하며 다음을 출력한다.

색 $C$ 를 추가하는 연산이면 add(C)를 출력한다.
색 $C$ 를 찾는 연산이면 find(C) = R를 출력한다. 여기서 $R$ 은 팔레트의 색 중 $C$ 와의 유사도(일치하는 비트 수)가 가장 큰 색이다. 그런 색이 여러 개이면 $R$ 은 그중 값이 가장 작은 색이다.

마지막으로 done()을 출력한다. find 연산은 팔레트에 색이 최소 한 개 있을 때만 주어진다.

예제2

예제 1

입력

예상 출력

init(2, 3)
add(1)
find(0) = 1
find(1) = 1
done()

예제 2

입력

예상 출력

init(3, 5)
add(0)
add(7)
find(1) = 0
add(1)
find(1) = 1
done()