Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 512 MB Toplam puan: 100
İstatistikler

Andriana hadde en vakker syklisk tabell $a = (a_0, a_1, \dots, a_{n-1})$ med $n$ heltall, der $0 \le a_i < 2^b$ for alle $0 \le i < n$, men dessverre mistet hun den! For oss er dette imidlertid ganske heldig, for uten disse glemsomme hovedpersonene ville verden hatt langt færre rekonstruksjonsoppgaver.

I mellomtiden har Andrianas venn Bob noen nyttige opplysninger: han hadde en notatbok der han noterte bitvise AND-verdier av påfølgende segmenter fra Andrianas tabell. En dag kjedet Bob seg ganske mye, så han skrev ned, for hver posisjon $i$ og en fast lengde $k$ ($k \le n$), verdien $$x_i = a_i \text{ AND } a_{i+1} \text{ AND } \dots \text{ AND } a_{i+k-1},$$ (der indeksene tas modulo $n$, siden tabellen er syklisk). Det er ukjent om Bob skaffet seg disse AND-verdiene på lovlig vis.

Andriana vil vite hva den største verdien av $k$ er slik at Bobs notatbok vil inneholde nok informasjon til å entydig rekonstruere hennes kjære opprinnelige tabell?

Inndata

Den første linjen i inndataene inneholder to heltall $n$ og $b$, der $n$ er lengden på Andrianas tapte tabell og $b$ er parameteren som definerer begrensningen $0 \le a_i < 2^b$. Den andre linjen inneholder $n$ heltall $a_i$ — elementene i den sykliske tabellen.

Utdata

Skriv ut et enkelt heltall — den største verdien av $k$ slik at tabellen $a$ kan rekonstrueres entydig fra tabellen $x$ med segment-AND-verdier.

Begrensninger

$3 \le n \le 2 \cdot 10^5$, $1 \le b \le 30$, $0 \le a_i < 2^b$.

Eksempler

Inndata 1

6 3
7 3 7 7 3 7

Utdata 1

2

Merk

I eksempelet er $n = 6, b = 3$. Tabellen $a = [7, 3, 7, 7, 3, 7]$ har binærrepresentasjonen $[111_2, 011_2, 111_2, 111_2, 011_2, 111_2]$, med tre biter for hvert element.

For $k = 2$ ville tabellen $x$ vært $[3, 3, 7, 3, 3, 7]$ (der $x_i = a_i \text{ AND } a_{(i+1) \bmod 6}$). Fra tabellen $x$ og verdien av $b$ kan vi entydig rekonstruere $a$.

For $k = 3$ ville tabellen $x$ vært $[3, 3, 3, 3, 3, 3]$, noe som ikke entydig bestemmer $a$ (for eksempel ville $[3, 3, 7, 3, 7, 7]$ gitt samme $x$).

Derfor er svaret for dette eksempelet $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.