문제
안나와 브루노는 고고학자이다.
두 사람은 지금 한 유적지를 탐사 중이다.
안나의 역할은 유적지로 가서 실제 유적을 보고 관측 결과를 수집해 본부로 보내는 것이다.
브루노의 역할은 본부에서 그 정보를 받아 분석하는 것이다.
그들의 조사는 앞으로 Q일 동안 이어질 것이다.
안나는 매일 자신이 조사한 결과로 음이 아닌 정수 X를 본부로 보내야 한다.
안나는 정보를 전송하기 위해 자신의 통신 장비를 이용한다.
통신 장비를 사용하면 하루에 한 번 본부로 N개의 0 또는 1로 이루어진 문자열을 보낼 수 있다.
그런데, 문제가 하나 발생했다. 안나의 통신 장비가 오래되어 망가졌다는 것이다.
구체적으로, 안나가 보내는 N개의 자리 중 L개에 해당하는 부품이 망가져 그 자리들은 안나의 행동과 관련없이 무조건 0을 보내게 된다.
또, 통신 장비의 상태는 그때 그때 달라져 매일 망가진 위치가 바뀔 수 있다.
안나는 자신의 장비 중 망가진 자리가 어느 위치인지 정확히 알고 있다.
하지만 브루노는 안나의 장비가 구체적으로 어느 위치에서 망가졌는지는 알지 못한다.
여러분은 두 사람을 도와 안나가 정보를 전달하는 것을 도와 주도록 하자.
입력
여러분의 코드는 표준 입출력을 사용하지 않으며, main 함수를 작성하지 않는다.
여러분은 "Annalib.h", "Brunolib.h" 헤더를 include하고 안나와 브루노의 행동을 묘사하는 다음의 함수들을 작성해야 한다.
void Anna(int N, long long X, int L, int P[]) :
이 함수는 인자로 N, X, L 그리고 망가진 자리들을 나타내는 P가 주어질 때 적절히 통신 장비를 사용해야 한다.
P는 길이 L의 배열로 망가진 자리들의 번호를 담고 있다. (장비의 자리들은 0~N-1번째로 표현)
Anna의 내부에서는 채점기의 함수 Set(int pos, int bit)를 호출해 장비를 사용할 수 있다.
Set(pos, bit)를 호출하면 장비의 pos번째 자리로 bit (= 0 또는 1)를 보낸다는 의미이다.
pos번째 자리가 존재치 않거나, bit로 0/1만을 넘겨야 한다.
또한, Anna함수는 한번 호출될 때마다 정확히 N번 Set을 호출해 모든 자리에 대한 정보를 남겨야 한다.
위 사항에 어긋난다면 0점을 받는다.
long long Bruno(int N, int A[]) :
이 함수는 인자로 N과 안나가 보낸 문자열인 A가 주어질 때 안나가 보내려고 했던 정수 X를 찾아 리턴해야 한다.
A[0]부터 A[N-1]까지에는 안나가 보낸 문자열의 각 자리가 0/1로 들어있다.
만약 채점기가 이 함수를 호출했을 때 X를 찾지 못한다면 0점을 받는다.
전역변수 등의 Set 함수 이외에 다른 수단을 이용하여 정보를 전달해서는 안된다.
다음은 문제의 제한 조건이다.
N = 150
Q = 1000
0 <= L <= 40
0 <= X <= 10^18
0 <= P[i] <= N-1 (0 <= i < K)
P[i] <= P[i+1] (0 <= i < K-1)
로그인해야 코드를 작성할 수 있어요.