Universal Cup Judging System

Universal Cup

Time Limit: 1.0 s Memory Limit: 512 MB Total points: 100
Statistics

Andriana memiliki sebuah larik siklik yang indah $a = (a_0, a_1, \dots, a_{n-1})$ yang terdiri dari $n$ bilangan bulat, di mana $0 \le a_i < 2^b$ untuk semua $0 \le i < n$, tetapi sayangnya ia kehilangannya! Namun bagi kita, hal ini cukup menguntungkan, karena tanpa tokoh utama yang pelupa seperti ini, dunia akan memiliki jauh lebih sedikit soal rekonstruksi.

Sementara itu, teman Andriana yang bernama Bob memiliki informasi berguna: ia menyimpan sebuah buku catatan tempat ia mencatat nilai bitwise AND dari segmen-segmen berurutan pada larik Andriana. Suatu hari Bob merasa cukup bosan, sehingga ia menuliskan, untuk setiap posisi $i$ dan suatu panjang tetap $k$ ($k \le n$), nilai $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (di mana indeks diambil modulo $n$, karena lariknya bersifat siklik). Tidak diketahui apakah Bob memperoleh nilai-nilai AND ini melalui cara yang sah.

Andriana ingin mengetahui berapakah nilai terbesar dari $k$ sedemikian sehingga buku catatan Bob berisi informasi yang cukup untuk merekonstruksi larik aslinya yang berharga secara tunggal?

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ dan $b$, di mana $n$ adalah panjang larik Andriana yang hilang dan $b$ adalah parameter yang mendefinisikan batasan $0 \le a_i < 2^b$. Baris kedua berisi $n$ bilangan bulat $a_i$ — elemen-elemen dari larik siklik tersebut.

Keluaran

Cetak sebuah bilangan bulat — nilai terbesar dari $k$ sedemikian sehingga larik $a$ dapat direkonstruksi secara tunggal dari larik $x$ yang berisi nilai AND segmen.

Batasan

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

Contoh

Masukan 1

6 3
7 3 7 7 3 7

Keluaran 1

2

Catatan

Pada kasus contoh, $n = 6, b = 3$. Larik $a = [7, 3, 7, 7, 3, 7]$ memiliki representasi biner $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, dengan menggunakan tiga bit untuk setiap elemen.

Untuk $k = 2$, larik $x$ adalah $[3, 3, 7, 3, 3, 7]$ (di mana $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Dari larik $x$ dan nilai $b$, kita dapat merekonstruksi $a$ secara tunggal.

Untuk $k = 3$, larik $x$ adalah $[3, 3, 3, 3, 3, 3]$, yang tidak menentukan $a$ secara tunggal (sebagai contoh, $[3, 3, 7, 3, 7, 7]$ akan menghasilkan $x$ yang sama).

Oleh karena itu, untuk contoh ini, jawabannya adalah $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.