Anna e Bruno sono maestri del gioco d'azzardo. Giocheranno una partita con D-taro, che è il mazziere del gioco.

In questo gioco, Anna e Bruno si trovano in stanze diverse. Possono comunicare tra loro solo utilizzando un dispositivo rotto. D-taro dà un intero ad Anna. Per Anna e Bruno, lo scopo di questo gioco è inviare l'intero ricevuto da Anna a Bruno utilizzando il dispositivo.

Quando il gioco inizia, all'inizio Anna dichiara un intero $m$ compreso tra $1$ e $2\,000$, inclusi. Poi giocano $Q$ turni. Il turno $i$ ($1\le i\le Q$) si svolge come segue.

1. D-taro dà un intero $A_i$ ad Anna.
2. Anna inserisce due array $s_i,t_i$ nel dispositivo. Ogni elemento degli array $s_i,t_i$ deve essere $0$ oppure $1$. Gli array $s_i,t_i$ devono avere la stessa lunghezza, e la lunghezza è compresa tra $1$ e $m$, inclusi.
3. Sia $u_i$ un array ottenuto dagli array $s_i$ e $t_i$ tramite mescolamento all'americana (riffle shuffle, vedi sotto). Allora il dispositivo invia $u_i$ a Bruno.
4. Bruno invia un intero a D-taro. Se questo intero è uguale all'intero $A_i$ dato da D-taro ad Anna, Anna e Bruno vincono questo turno.

Scrivi dei programmi che implementino le strategie di Anna e Bruno in modo che vincano tutti i $Q$ turni.

Mescolamento all'americana

Diciamo che un array $Z$ è ottenuto dagli array $X$ e $Y$ tramite mescolamento all'americana se possiamo dividere gli elementi dell'array $Z$ in due gruppi in modo che siano soddisfatte le seguenti due condizioni.

• L'array costituito dagli elementi del primo gruppo nello stesso ordine è uguale all'array $X$.
• L'array costituito dagli elementi del secondo gruppo nello stesso ordine è uguale all'array $Y$.

Ad esempio, l'array $Z=[1,1,1,0,0,0]$ è ottenuto da $X=[1,1,0]$ e $Y=[1,0,0]$ tramite mescolamento all'americana perché l'array costituito dal primo, secondo e quarto elemento di $Z$ nello stesso ordine è l'array $[1,1,0]$, e l'array costituito dal terzo, quinto e sesto elemento di $Z$ nello stesso ordine è l'array $[1,0,0]$.

D'altra parte, se $X=[1,1,0]$, $Y=[1,0,0]$ e $Z=[0,0,0,1,1,1]$, l'array $Z$ non è ottenuto da $X$ e $Y$ tramite mescolamento all'americana.

Dettagli di implementazione

Devi inviare due file.

Il primo file è Anna.cpp. Deve implementare la strategia di Anna. Deve implementare le seguenti funzioni. Il programma deve includere Anna.h usando la direttiva del preprocessore #include.

• int Declare()

  Questa funzione viene chiamata una volta all'inizio.

  • Il valore restituito è l'intero $m$ dichiarato da Anna.
  • L'intero $m$ deve essere compreso tra $1$ e $2\,000$, inclusi. Se questa condizione non è soddisfatta, il tuo programma viene giudicato come Wrong Answer [1].

• std::pair<std::vector<int>, std::vector<int> > Anna(long long A)

  Dopo che la funzione Declare è stata chiamata, questa funzione viene chiamata $Q$ volte. L'$i$-esima chiamata ($1\le i\le Q$) a questa funzione corrisponde al Passo 1 e al Passo 2 per il turno $i$.

  • Il parametro A è l'intero $A_i$ dato da D-taro ad Anna.
  • Il valore restituito è la coppia dei due array $s_i,t_i$ inseriti da Anna nel dispositivo.
  • Ogni elemento degli array $s_i,t_i$ deve essere $0$ oppure $1$. Se questa condizione non è soddisfatta, il tuo programma viene giudicato come Wrong Answer [2].
  • Entrambe le lunghezze degli array $s_i,t_i$ devono essere comprese tra $1$ e $m$, inclusi. Se questa condizione non è soddisfatta, il tuo programma viene giudicato come Wrong Answer [3].
  • Gli array $s_i,t_i$ devono avere la stessa lunghezza. Se questa condizione non è soddisfatta, il tuo programma viene giudicato come Wrong Answer [4].

Il secondo file è Bruno.cpp. Deve implementare la strategia di Bruno. Deve implementare la seguente funzione. Il programma deve includere Bruno.h usando la direttiva del preprocessore #include.

• long long Bruno(std::vector<int> u)

  Dopo che Anna ha inserito gli array nel dispositivo, questa funzione viene chiamata una volta. In totale, questa funzione viene chiamata $Q$ volte. L'$i$-esima chiamata ($1\le i\le Q$) a questa funzione corrisponde al Passo 3 e al Passo 4 per il turno $i$.

  • Il parametro u è l'array $u_i$ inviato dal dispositivo a Bruno per il turno $i$.
  • Il valore restituito è l'intero inviato da Bruno a D-taro.
  • Il valore restituito deve essere uguale all'intero $A_i$ dato da D-taro ad Anna. Se questa condizione non è soddisfatta, il tuo programma viene giudicato come Wrong Answer [5].

Avvisi importanti

• Il tuo programma può implementare altre funzioni per uso interno, o usare variabili globali. I file inviati verranno compilati con il grader e diventeranno un unico file eseguibile. Tutte le variabili globali e le funzioni interne devono essere dichiarate in un namespace anonimo (unnamed namespace) per evitare conflitti con altri file. Quando viene valutato, verrà eseguito come due processi distinti per Anna e Bruno. Il processo di Anna e il processo di Bruno non possono condividere variabili globali.
• Il tuo programma non deve usare lo standard input e lo standard output. Il tuo programma non deve comunicare con altri file con alcun metodo. Tuttavia, il tuo programma può stampare informazioni di debug sullo standard error.

Compilazione e test di esecuzione

Puoi scaricare un file archivio dalla pagina web della gara che contiene il grader di esempio per testare il tuo programma. Il file archivio contiene anche un file sorgente di esempio del tuo programma.

Il grader di esempio è il file grader.cpp. Per testare il tuo programma, metti grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h nella stessa directory ed esegui il seguente comando per compilare i tuoi programmi.

g++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Quando la compilazione va a buon fine, viene generato il file eseguibile grader.

Nota che il grader effettivo è diverso dal grader di esempio. Il grader di esempio verrà eseguito come un singolo processo, che leggerà i dati di input dallo standard input e scriverà i risultati sullo standard output.

Input per il grader di esempio

Il grader di esempio legge i seguenti dati dallo standard input.

$$ \begin{gathered} Q\\ A_1\\ A_2\\ \vdots\\ A_Q \end{gathered} $$

Output del grader di esempio

Il grader di esempio stampa le seguenti informazioni sullo standard output (virgolette per chiarezza).

• Se il tuo programma è giudicato corretto, scrive il valore restituito $m$ della funzione Declare come “Accepted: 2000”.
• Se il tuo programma è giudicato come uno qualsiasi dei Wrong Answer, il grader di esempio scrive il suo tipo come “Wrong Answer [1]”.

Se il tuo programma soddisfa le condizioni di diversi tipi di Wrong Answer, il grader di esempio ne segnala solo uno.

Quando viene eseguito il grader di esempio, il mescolamento all'americana per ciascun turno viene calcolato usando numeri pseudocasuali. I loro risultati non cambiano tra le esecuzioni. Per cambiare il seme dei numeri pseudocasuali, esegui il grader di esempio nel modo seguente.

./grader 2022

Il primo argomento deve essere un intero.

Vincoli

• $1\le Q\le 1\,000$.
• $1\le A_i\le 1\,000\,000\,000\,000\,000\,000\ (=10^{18})$ ($1\le i\le Q$).

Subtask

1. (5 punti) $A_i\le 2\,000$ ($1\le i\le Q$).
2. (5 punti) $A_i\le 4\,000\,000$ ($1\le i\le Q$).
3. (3 punti) $A_i\le 10\,000\,000\ (=10^7)$ ($1\le i\le Q$).
4. (12 punti) $A_i\le 100\,000\,000\ (=10^8)$ ($1\le i\le Q$).
5. (15 punti) $A_i\le 100\,000\,000\,000\ (=10^{11})$ ($1\le i\le Q$).

6. (60 punti) Nessun vincolo aggiuntivo. Per questo subtask, il tuo punteggio viene calcolato come segue.

   • Sia $m^*$ il massimo degli interi $m$ dichiarati da Anna per tutti i casi di test di questo subtask.
   • Il tuo punteggio è il seguente.

Esempi

Ecco un input di esempio per il grader di esempio e le corrispondenti chiamate di funzione.

Input 1

2
42
2000

Chiamate di funzione di esempio

In questo input di esempio ci sono $Q\ (=2)$ turni. Per il turno 1, D-taro dà l'intero $A_1\ (=42)$ ad Anna. Per il turno 2, D-taro dà l'intero $A_2\ (=2000)$ ad Anna.

Questo input di esempio soddisfa i vincoli di tutti i subtask.