Aidos는 퍼즐을 만들어 Temirulan에게 해결하도록 도전장을 내밀었습니다. 그는 $1$부터 $n$까지 번호가 매겨진 $n$개의 서로 다른 음이 아닌 정수로 이루어진 수열 $a = a_1, a_2, \dots, a_n$을 선택했습니다.
Temirulan은 다음 두 가지 유형의 질문을 할 수 있습니다.
ask— 주어진 수열의 $i$번째 위치에 있는 숫자를 알아냅니다.get_pairwise_xor— 서로 다른 정수들의 수열 $i_1, i_2, \dots, i_k$가 주어지면, 수열 $a$의 인덱스 $i_1, i_2, \dots, i_k$에 해당하는 원소들의 쌍에 대한 XOR 값의 집합 $\{a_{i_x} \oplus a_{i_y} \mid 1 \le x, y \le k\}$를 구합니다.
예를 들어, Aidos가 수열 $[1, 5, 6, 3]$을 선택했다고 가정해 봅시다. 그러면 ask(2) 질문에 대해 Aidos는 숫자 $5$를 답할 것이고, get_pairwise_xor({3, 4}) 질문에 대해서는 다음 이유로 인해 수열 $[0, 0, 5, 5]$를 답할 것입니다.
- $a_3 \oplus a_4 = 6 \oplus 3 = 5$
- $a_4 \oplus a_3 = 3 \oplus 6 = 5$
- $a_3 \oplus a_3 = 6 \oplus 6 = 0$
- $a_4 \oplus a_4 = 3 \oplus 3 = 0$
Temirulan은 이 퍼즐을 해결하지 못했고, 당신의 임무는 그를 돕는 것입니다. 위에서 설명한 질문들을 사용하여 숨겨진 수열을 찾으십시오.
입력
제출한 프로그램은 표준 입력에서 읽거나 표준 출력에 출력하거나 다른 파일과 상호작용해서는 안 됩니다.
당신은 다음 함수를 구현해야 합니다: int[] guess(int n)
- $n$: 숨겨진 수열의 길이.
- 이 함수는 각 테스트 케이스마다 정확히 한 번 호출됩니다.
- 이 함수는 숨겨진 수열을 원래 순서대로 반환해야 합니다.
당신의 함수는 다음 함수들을 호출할 수 있습니다:
int ask(int i)- $i$: 수열 내 숫자의 인덱스, $1 \le i \le n$.
- 이 함수는 숨겨진 수열의 $i$번째 숫자를 반환합니다.
int[] get_pairwise_xor(int[] pos)- $pos$: 수열의 인덱스들로 이루어진 비어 있지 않은 리스트.
- $pos$의 모든 원소는 서로 다른 정수여야 합니다.
- $k$를 $pos$의 원소 개수라고 하면, 각 $1 \le i \le k$에 대해 $1 \le pos_i \le n$입니다.
- 이 함수는 $k^2$개의 원소로 이루어진 정렬된 리스트를 반환합니다: XOR 쌍의 집합 $\{a_{pos_x} \oplus a_{pos_y} \mid 1 \le x, y \le k\}$.
각 테스트 케이스마다 두 함수를 합쳐서 최대 $200$번까지만 호출할 수 있습니다. 위 조건 중 하나라도 위반하면 프로그램은 오답(Wrong Answer) 판정을 받습니다. 그렇지 않으면 정답(Accepted) 판정을 받으며, 점수는 ask 및 get_pairwise_xor 함수를 호출한 총 횟수에 따라 계산됩니다("서브태스크" 섹션 참조).
제한
- $2 \le n \le 100$
- 각 $1 \le i \le n$에 대해 $0 \le a_i \le 10^9$.
이 문제에서 채점기는 적응형(adaptive)이 아닙니다. 즉, 수열 $a$는 채점기가 실행될 때 처음에 고정되며, 프로그램의 호출에 따라 변하지 않습니다.
서브태스크
- (6점) $n \le 4$
- (94점) 추가 제한 없음. 이 서브태스크에서 점수는 다음과 같은 방식으로 계산됩니다. $q$를
ask및get_pairwise_xor함수를 호출한 총 횟수라고 합시다.- $q \le 15$이면, 점수는 $94$점입니다.
- $15 < q \le 40$이면, 점수는 $84 - 2(q - 16)$점입니다.
- $40 < q \le 50$이면, 점수는 $35$점입니다.
- 그 외의 경우, 점수는 $0$점입니다.
각 서브태스크의 점수는 해당 서브태스크의 모든 테스트 케이스 결과 중 최소 점수입니다.
참고
XOR 연산은 비트 단위 배타적 논리합(bitwise exclusive OR)입니다.
숨겨진 수열 $a$가 $[1, 5, 6, 3]$이라고 가정합시다. 채점기가 함수를 호출합니다. 상호작용의 예시는 다음과 같습니다.
| 호출 | 결과 |
|---|---|
ask(2) |
$5$ |
get_pairwise_xor({1, 2, 3}) |
$\{0, 0, 0, 3, 3, 4, 4, 7, 7\}$ |
ask(3) |
$6$ |
get_pairwise_xor({4, 2}) |
$\{0, 0, 6, 6\}$ |
get_pairwise_xor({2}) |
$\{0\}$ |
샘플 채점기는 다음 형식으로 입력을 읽습니다: 1행: $n$ 2행: $a_1, a_2, \dots, a_n$
시스템에서 Java, C++11, FPC, Python 2 언어에 대한 예제가 포함된 xoractive.zip을 다운로드할 수 있습니다.
함수 호출에 대한 모든 예제는 위에서 확인할 수 있습니다. Python 2의 경우, def guess(n, interactor) 함수를 구현해야 하며, 여기서 interactor는 테스트 중인 클래스의 인스턴스입니다. ask와 get_pairwise_xor는 이 클래스의 메서드입니다.
xoractive.zip에는 각 언어에 대한 솔루션 예제가 포함되어 있습니다.
Java 언어 솔루션의 경우, 파일명과 클래스명은 각각 Xoractive.java와 Xoractive여야 합니다.
Pascal 언어 솔루션의 경우, 파일명은 xoractive.pas여야 합니다.