Nella fabbrica della JOI Co., Ltd. ci sono $N$ tavoli, numerati da $0$ a $N-1$. Nella fabbrica ci sono $N-1$ nastri trasportatori, numerati da $0$ a $N-2$. Il nastro trasportatore $i$ ($0 \le i \le N-2$) collega il tavolo $A_i$ e il tavolo $B_i$. Esso trasporta i prodotti da un tavolo all'altro. Tuttavia, non possiamo vedere la direzione di trasporto. Se ignoriamo le direzioni dei nastri trasportatori, ogni coppia di tavoli è collegata da un certo numero di nastri trasportatori.

IOI-kun è il direttore della fabbrica. Poiché ha dimenticato la direzione di trasporto di ogni nastro trasportatore, eseguirà più volte la seguente sequenza di operazioni.

1. Sceglie un certo numero di nastri trasportatori e inverte le direzioni di trasporto dei nastri trasportatori scelti.
2. Sceglie un certo numero di tavoli e posiziona un prodotto su ciascun tavolo scelto.

3. Per ogni tavolo su cui è stato posizionato un prodotto, si verifica simultaneamente uno dei seguenti eventi.

   • Se non c'è alcun nastro trasportatore che trasporta prodotti a partire da esso, non accade nulla.
   • Se ci sono nastri trasportatori che trasportano prodotti a partire da esso, il prodotto sul tavolo viene trasportato da uno di tali nastri trasportatori. Il prodotto si ferma al tavolo di destinazione del nastro trasportatore. Il prodotto non si muoverà più.

4. IOI-kun verifica per ciascun tavolo se su di esso siano presenti uno o più prodotti. Se ci sono prodotti su un tavolo, IOI-kun li raccoglie tutti.

5. Per ogni nastro trasportatore la cui direzione è stata invertita nell'operazione 1., IOI-kun ripristina la direzione. La sua direzione torna a essere quella originale.

IOI-kun vuole determinare la direzione originale di ogni nastro trasportatore eseguendo la sequenza di operazioni sopra descritta al massimo $30$ volte.

Scrivi un programma che, ricevute le informazioni sui tavoli collegati dai nastri trasportatori, implementi la strategia di IOI-kun per determinare la direzione originale di ogni nastro trasportatore eseguendo la sequenza di operazioni sopra descritta al massimo $30$ volte.

Dettagli di implementazione

Devi inviare un solo file.

Il file è conveyor.cpp. Esso deve implementare la seguente funzione. Il programma deve includere conveyor.h utilizzando la direttiva del preprocessore #include.

In conveyor.cpp deve essere implementata la seguente funzione.

• void Solve(int N, std::vector<int> A, std::vector<int> B)

  Questa funzione viene chiamata una sola volta per ogni caso di test.

  • Il parametro N è il numero di tavoli $N$.
  • I parametri A, B sono array di lunghezza $N-1$, che descrivono i tavoli collegati dai nastri trasportatori.

  Il tuo programma può chiamare le seguenti funzioni.

  • std::vector<int> Query(std::vector<int> x, std::vector<int> y)

    Utilizzando questa funzione, IOI-kun esegue le operazioni nella fabbrica.

    • Il parametro x è un array di lunghezza $N-1$. Per $0 \le i \le N-2$, IOI-kun inverte la direzione del nastro trasportatore $i$ se x[i] = 1, e non inverte la direzione del nastro trasportatore $i$ se x[i] = 0.
    • Il parametro y è un array di lunghezza $N$. Per $0 \le j \le N-1$, IOI-kun posiziona un prodotto sul tavolo $j$ se y[j] = 1, e non posiziona alcun prodotto sul tavolo $j$ se y[j] = 0.
    • Sia z il valore restituito da questa funzione. È un array di lunghezza $N$. Per $0 \le j \le N-1$, ci sono uno o più prodotti sul tavolo $j$ se z[j] = 1, e non c'è alcun prodotto sul tavolo $j$ se z[j] = 0.
    • La lunghezza dell'array x deve essere uguale a $N-1$. Se questa condizione non è soddisfatta, il tuo programma viene valutato come Wrong Answer [1].
    • Ogni elemento dell'array x deve essere 0 oppure 1. Se questa condizione non è soddisfatta, il tuo programma viene valutato come Wrong Answer [2].
    • La lunghezza dell'array y deve essere uguale a $N$. Se questa condizione non è soddisfatta, il tuo programma viene valutato come Wrong Answer [3].
    • Ogni elemento dell'array y deve essere 0 oppure 1. Se questa condizione non è soddisfatta, il tuo programma viene valutato come Wrong Answer [4].
    • La funzione Query non deve essere chiamata più di $30$ volte. Se viene chiamata più di $30$ volte, il tuo programma viene valutato come Wrong Answer [5].

  • void Answer(std::vector<int> a)

    Utilizzando questa funzione, IOI-kun comunica la direzione originale di ciascun nastro trasportatore.

    • Il parametro a è un array di lunghezza $N-1$. Per $0 \le i \le N-2$, il nastro trasportatore $i$ trasporta prodotti da $A_i$ a $B_i$ se a[i] = 0, mentre trasporta prodotti da $B_i$ ad $A_i$ se a[i] = 1.
    • La lunghezza dell'array a deve essere uguale a $N-1$. Se questa condizione non è soddisfatta, il tuo programma viene valutato come Wrong Answer [6].
    • Ogni elemento dell'array a deve essere 0 oppure 1. Se questa condizione non è soddisfatta, il tuo programma viene valutato come Wrong Answer [7].
    • Se IOI-kun comunica una direzione errata per un nastro trasportatore, il tuo programma viene valutato come Wrong Answer [8].
    • La funzione Answer deve essere chiamata esattamente una volta. Se la funzione Answer viene chiamata più di una volta, il tuo programma viene valutato come Wrong Answer [9]. Quando la funzione Solve termina, se la funzione Answer non è stata chiamata, il tuo programma viene valutato come Wrong Answer [10].

Avvertenze importanti

• Il tuo programma può implementare altre funzioni per uso interno o utilizzare variabili globali.
• Il tuo programma non deve utilizzare lo standard input né lo standard output. Il tuo programma non deve comunicare con altri file con alcun metodo. Tuttavia, il tuo programma può scrivere informazioni di debug sullo standard error.

Compilazione ed esecuzione di prova

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

Il grader di esempio è il file grader.cpp. Per testare il tuo programma, inserisci grader.cpp, conveyor.cpp, conveyor.h nella stessa directory ed esegui il seguente comando per compilare i tuoi programmi. In alternativa, puoi eseguire compile.sh contenuto nel file di archivio.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.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{array}{llll} N \\ A_0 & A_1 & \cdots & A_{N-2} \\ B_0 & B_1 & \cdots & B_{N-2} \\ C_0 & C_1 & \cdots & C_{N-2} \end{array} $$

Per $0 \le i \le N-2$, abbiamo $C_i=0$ se il nastro trasportatore $i$ trasporta prodotti dal tavolo $A_i$ al tavolo $B_i$. Altrimenti, abbiamo $C_i=1$.

Output del grader di esempio

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

• Se il tuo programma viene valutato come corretto, riporta il numero di chiamate alla funzione Query come “Accepted: 22”.
• Se il tuo programma viene valutato come un qualsiasi tipo di Wrong Answer, il grader di esempio scrive il suo tipo come “Wrong Answer [4]”.

Se il tuo programma soddisfa le condizioni di più tipi di Wrong Answer, il grader di esempio ne riporta solo uno.

Nel grader di esempio, tra i nastri trasportatori che trasportano prodotti dal tavolo su cui è posizionato un prodotto, il nastro trasportatore che trasporta effettivamente il prodotto viene scelto in modo uniforme e casuale tramite numeri pseudocasuali i cui risultati non cambiano tra diverse esecuzioni. Per cambiare il seme (seed) dei numeri pseudocasuali, esegui il grader di esempio passando un argomento intero come segue.

./grader 2023

Note sulla valutazione

Per alcuni casi di test, il grader effettivo è adattivo. Ciò significa che il grader non ha una risposta fissata all'inizio, ma risponde in base alle precedenti chiamate alla funzione Query. È garantito che esista almeno una risposta che non contraddice tutte le risposte del grader.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni.

• $0 \le A_i \le N-1$ ($0 \le i \le N-2$).
• $0 \le B_i \le N-1$ ($0 \le i \le N-2$).
• Se ignoriamo le direzioni dei nastri trasportatori, ogni coppia di tavoli è collegata da un certo numero di nastri trasportatori.

Subtask

1. (1 punto) $N=2$.
2. (14 punti) $N=30$.
3. (10 punti) $N=100\,000$, $A_i=i$ ($0 \le i \le N-2$), $B_i=i+1$ ($0 \le i \le N-2$).
4. (75 punti) $N=100\,000$.

Esempio di comunicazione

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

Input 1

3
0 2
2 1
1 0

Chiamate di funzione di esempio

Per la prima chiamata alla funzione Query, un altro possibile valore restituito oltre a [1, 0, 0] è [0, 1, 0].

Per la seconda chiamata alla funzione Query, il prodotto sul tavolo $0$ viene trasportato al tavolo $2$ passando attraverso il nastro trasportatore $0$, e lì si ferma. Nota che questo prodotto non verrà trasportato al tavolo $1$ passando attraverso il nastro trasportatore $1$.

Nota che questo input di esempio non soddisfa i vincoli di alcun subtask.

Tra i file che possono essere ottenuti dalla pagina web della gara, sample-02.txt soddisfa i vincoli del Subtask $1$, e sample-03.txt soddisfa i vincoli del Subtask $2$.