Universal Cup Judging System

Universal Cup

시간 제한: 1.0 s 메모리 제한: 512 MB 총점: 100
통계

Andriana hatte ein wunderschönes zyklisches Array $a = (a_0, a_1, \dots, a_{n-1})$ aus $n$ ganzen Zahlen, wobei $0 \le a_i < 2^b$ für alle $0 \le i < n$ galt, aber leider hat sie es verloren! Für uns ist das jedoch ein großes Glück, denn ohne diese vergesslichen Protagonisten gäbe es auf der Welt viel weniger Rekonstruktionsprobleme.

Unterdessen hat Andrianas Freund Bob einige nützliche Informationen: Er führte ein Notizbuch, in dem er die bitweisen AND-Werte aufeinanderfolgender Teilabschnitte aus Andrianas Array notierte. Eines Tages war Bob ziemlich gelangweilt, also schrieb er für jede Position $i$ und eine feste Länge $k$ ($k \le n$) den Wert $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ auf (wobei die Indizes modulo $n$ genommen werden, da das Array zyklisch ist). Es ist nicht bekannt, ob Bob diese AND-Werte auf legalem Wege erworben hat.

Andriana möchte wissen, was der größte Wert von $k$ ist, sodass Bobs Notizbuch genügend Informationen enthält, um ihr geschätztes ursprüngliches Array eindeutig zu rekonstruieren.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n$ und $b$, wobei $n$ die Länge von Andrianas verlorenem Array ist und $b$ der Parameter ist, der die Bedingung $0 \le a_i < 2^b$ definiert. Die zweite Zeile enthält $n$ ganze Zahlen $a_i$ — die Elemente des zyklischen Arrays.

Ausgabe

Gib eine einzige ganze Zahl aus — den größten Wert von $k$, sodass das Array $a$ eindeutig aus dem Array $x$ der Abschnitt-AND-Werte rekonstruiert werden kann.

Beschränkungen

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

Beispiele

Eingabe 1

6 3
7 3 7 7 3 7

Ausgabe 1

2

Hinweis

Im Beispiel gilt $n = 6, b = 3$. Das Array $a = [7, 3, 7, 7, 3, 7]$ hat die Binärdarstellung $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, wenn man drei Bits für jedes Element verwendet.

Für $k = 2$ wäre das Array $x$ gleich $[3, 3, 7, 3, 3, 7]$ (wobei $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Aus dem Array $x$ und dem Wert von $b$ können wir $a$ eindeutig rekonstruieren.

Für $k = 3$ wäre das Array $x$ gleich $[3, 3, 3, 3, 3, 3]$, was $a$ nicht eindeutig bestimmt (zum Beispiel würde $[3, 3, 7, 3, 7, 7]$ dasselbe $x$ liefern).

Daher lautet die Antwort für dieses Beispiel $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.