Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 512 MB مجموع النقاط: 100
الإحصائيات

Andriana는 모든 $0 \le i < n$에 대해 $0 \le a_i < 2^b$를 만족하는 $n$개의 정수로 이루어진 아름다운 원형 배열 $a = (a_0, a_1, \dots, a_{n-1})$을 가지고 있었지만, 불행히도 그것을 잃어버렸습니다! 하지만 우리에게는 꽤 다행스러운 일인데, 이렇게 건망증이 심한 주인공들이 없었다면 세상에 복원 문제가 훨씬 적었을 것이기 때문입니다.

한편, Andriana의 친구 Bob은 유용한 정보를 가지고 있습니다. 그는 Andriana의 배열에서 연속한 구간들의 비트 AND 값을 기록한 공책을 가지고 있었습니다. 어느 날 심심했던 Bob은 모든 위치 $i$와 어떤 고정된 길이 $k$ ($k \le n$)에 대해 다음 값을 적어 두었습니다: $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (배열이 원형이므로 인덱스는 $n$으로 나눈 나머지로 취합니다). Bob이 이 AND 값들을 합법적인 수단으로 입수했는지는 알려져 있지 않습니다.

Andriana는 Bob의 공책에 그녀의 소중한 원래 배열을 유일하게 복원할 수 있을 만큼 충분한 정보가 담기게 되는 가장 큰 $k$의 값이 얼마인지 알고 싶어 합니다.

입력

입력의 첫 번째 줄에는 두 정수 $n$과 $b$가 주어지며, 여기서 $n$은 Andriana가 잃어버린 배열의 길이이고 $b$는 제약 조건 $0 \le a_i < 2^b$를 정의하는 매개변수입니다. 두 번째 줄에는 원형 배열의 원소를 나타내는 $n$개의 정수 $a_i$가 주어집니다.

출력

구간 AND 배열 $x$로부터 배열 $a$를 유일하게 복원할 수 있는 가장 큰 $k$의 값을 나타내는 정수 하나를 출력하세요.

제한

$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.

예제

입력 1

6 3
7 3 7 7 3 7

출력 1

2

참고

예제에서 $n = 6, b = 3$입니다. 배열 $a = [7, 3, 7, 7, 3, 7]$은 각 원소에 3비트를 사용하여 이진 표현으로 $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$가 됩니다.

$k = 2$일 때, 배열 $x$는 $[3, 3, 7, 3, 3, 7]$이 됩니다(여기서 $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). 배열 $x$와 $b$의 값으로부터 우리는 $a$를 유일하게 복원할 수 있습니다.

$k = 3$일 때, 배열 $x$는 $[3, 3, 3, 3, 3, 3]$이 되며, 이는 $a$를 유일하게 결정하지 못합니다(예를 들어, $[3, 3, 7, 3, 7, 7]$도 동일한 $x$를 만듭니다).

따라서 이 예제에 대한 답은 $k = 2$입니다.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.