XOR

시간 제한5초메모리 제한256 MB

요약

xor가 x 이상인 가장 긴 연속 구간을 찾아 시작 위치와 길이를 출력하며 동점이면 시작 위치가 가장 작은 구간을 선택합니다.

문제

길이가 $N$ 인 수열 $a_1, a_2, \ldots, a_N$ 과 정수 $x$ 가 주어진다. 연속한 원소의 xor가 $x$ 이상인 구간 중에서 가장 긴 것을 찾아라. 즉 다음 조건을 만족하면서 $k$ 가 최대인 $i$ 와 $k$ 를 구한다.

$a_i \oplus a_{i+1} \oplus \cdots \oplus a_{i+k-1} \ge x, \qquad 1 \le i \le i+k-1 \le N$

입력으로 주어지는 모든 데이터에는 조건을 만족하는 구간이 적어도 하나 있다.

xor( $\oplus$ )는 두 수를 이진법으로 적었을 때 같은 자리의 비트마다 다음 규칙을 적용한 결과다.

결과는 피연산자의 순서와 무관해서 $a \oplus b = b \oplus a$ 이고, $a \oplus (a \oplus b) = b$ 이다. 파스칼에서는 xor, C와 C++, 자바에서는 ^ 연산자로 쓴다.

첫째 줄에 $N$ 과 $x$ 가 주어진다. ( $1 \le N \le 250\,000$ , $0 \le x \le 10^9$ )

둘째 줄에 수열의 원소 $N$ 개가 공백으로 구분되어 주어진다. 각 원소는 $10^9$ 이하의 음이 아닌 정수다.

첫째 줄에 $i$ 와 $k$ 를 공백으로 구분해 출력한다. $k$ 가 최대인 답이 여러 개면 $i$ 가 가장 작은 것을 출력한다.