Universal Cup Judging System

Universal Cup

実行時間制限: 1.0 s メモリ制限: 512 MB 満点: 100
統計

ל-Andriana היה מערך מעגלי יפהפה $a = (a_0, a_1, \dots, a_{n-1})$ של $n$ מספרים שלמים, שבו $0 \le a_i < 2^b$ עבור כל $0 \le i < n$, אך למרבה הצער היא איבדה אותו! עם זאת, עבורנו זהו מזל גדול, שכן ללא הגיבורים השכחנים הללו, היו בעולם הרבה פחות בעיות שחזור.

בינתיים, לחברה של Andriana, Bob, יש מידע מועיל: הוא שמר מחברת שבה תיעד ערכי AND סיביות (bitwise 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.