Universal Cup Judging System

Universal Cup

Límite de tiempo: 1.0 s Límite de memoria: 512 MB Puntuación total: 100
Estadísticas

كان لدى Andriana مصفوفة دورية جميلة $a = (a_0, a_1, \dots, a_{n-1})$ مكونة من $n$ من الأعداد الصحيحة، حيث $0 \le a_i < 2^b$ لكل $0 \le i < n$، ولكنها للأسف فقدتها! ومع ذلك، بالنسبة لنا، هذا أمر محظوظ للغاية، فبدون هؤلاء الأبطال كثيري النسيان، لكان في العالم عدد أقل بكثير من مسائل إعادة البناء.

في هذه الأثناء، يمتلك Bob صديق Andriana بعض المعلومات المفيدة: فقد احتفظ بدفتر ملاحظات سجل فيه قيم عملية AND البتية لمقاطع متتالية من مصفوفة Andriana. كان 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 معرفة ما هي أكبر قيمة للعدد $k$ بحيث يحتوي دفتر ملاحظات Bob على معلومات كافية لإعادة بناء مصفوفتها الأصلية الثمينة بشكل فريد؟

الإدخال

يحتوي السطر الأول من الإدخال على عددين صحيحين $n$ و $b$، حيث $n$ هو طول مصفوفة Andriana المفقودة و $b$ هو المعامل الذي يحدد القيد $0 \le a_i < 2^b$. يحتوي السطر الثاني على $n$ من الأعداد الصحيحة $a_i$ — عناصر المصفوفة الدورية.

الإخراج

اطبع عددًا صحيحًا واحدًا — أكبر قيمة للعدد $k$ بحيث يمكن إعادة بناء المصفوفة $a$ بشكل فريد من المصفوفة $x$ لقيم AND للمقاطع.

القيود

$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.