Universal Cup Judging System

Universal Cup

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

Андрианада барлық $0 \le i < n$ үшін $0 \le a_i < 2^b$ болатын $n$ бүтін саннан тұратын әдемі циклдік $a = (a_0, a_1, \dots, a_{n-1})$ массиві болған еді, бірақ, өкінішке орай, ол оны жоғалтып алды! Дегенмен, біз үшін бұл өте сәтті жағдай, өйткені осындай ұмытшақ кейіпкерлер болмаса, әлемде қалпына келтіру есептері әлдеқайда аз болар еді.

Сол уақытта Андриананың досы Бобта пайдалы ақпарат бар: ол Андриананың массивіндегі қатар орналасқан кесінділердің бит бойынша ЖӘНЕ (AND) мәндерін жазып жүрген дәптерін сақтап қалған. Бір күні Бобтың іші пысып, әрбір $i$ позициясы мен белгілі бір тұрақты $k$ ($k \le n$) ұзындығы үшін мына мәнді жазып алды: $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (мұнда массив циклдік болғандықтан, индекстер $n$ модулі бойынша алынады). Бобтың бұл AND мәндерін заңды жолмен алғаны-алмағаны белгісіз.

Андриана Бобтың дәптерінде оның бағалы бастапқы массивін бірмәнді түрде қалпына келтіруге жеткілікті ақпарат болатындай ең үлкен $k$ мәні қандай екенін білгісі келеді.

Кіріс деректері

Кіріс деректерінің бірінші жолында екі бүтін сан $n$ және $b$ берілген, мұндағы $n$ — Андриананың жоғалған массивінің ұзындығы, ал $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.