Universal Cup Judging System

Universal Cup

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

Andriana は $n$ 個の整数からなる美しい巡回配列 $a = (a_0, a_1, \dots, a_{n-1})$(すべての $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$ の値がいくらであるかを知りたいと思っています。

入力

入力の最初の行には2つの整数 $n$ と $b$ が含まれます。ここで、$n$ は Andriana が失くした配列の長さであり、$b$ は制約 $0 \le a_i < 2^b$ を定めるパラメータです。 2行目には、巡回配列の要素を表す $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.