Universal Cup Judging System

Universal Cup

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

Andriana 原本有一個好靚嘅循環陣列 $a = (a_0, a_1, \dots, a_{n-1})$,入面有 $n$ 個整數,對於所有 $0 \le i < n$ 都滿足 $0 \le a_i < 2^b$,但好可惜佢唔見咗個陣列!不過對我哋嚟講,呢件事相當幸運,因為如果冇呢啲健忘嘅主角,世界上就會少好多重構問題。

與此同時,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]$ 嘅二進制表示為 $[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.