W fabryce JOI Co., Ltd. znajduje się $N$ stołów, ponumerowanych od $0$ do $N-1$. W fabryce jest też $N-1$ przenośników taśmowych, ponumerowanych od $0$ do $N-2$. Przenośnik $i$ ($0\le i\le N-2$) łączy stół $A_i$ ze stołem $B_i$. Transportuje produkty z jednego z tych stołów na drugi. Nie możemy jednak zobaczyć kierunku transportu. Jeśli pominiemy kierunki przenośników, każda para stołów jest połączona pewnym ciągiem przenośników.

IOI-kun jest dyrektorem fabryki. Ponieważ zapomniał kierunku transportu każdego przenośnika, kilkakrotnie wykona następującą sekwencję operacji.

1. Wybiera pewną liczbę przenośników i odwraca kierunki transportu wybranych przenośników.
2. Wybiera pewną liczbę stołów i kładzie po jednym produkcie na każdym wybranym stole.

3. Dla każdego stołu, na którym położono produkt, jednocześnie zachodzi jedno z poniższych zdarzeń.

   • Jeśli żaden przenośnik nie transportuje produktów z tego stołu, nic się nie dzieje.
   • Jeśli istnieją przenośniki transportujące produkty z tego stołu, produkt zostaje przetransportowany przez jeden z nich. Produkt zatrzymuje się na stole docelowym tego przenośnika i nie porusza się już dalej.
4. IOI-kun sprawdza, czy na każdym stole znajduje się co najmniej jeden produkt. Jeśli na stole są produkty, zabiera je wszystkie.
5. Dla każdego przenośnika, którego kierunek odwrócono w operacji 1, IOI-kun ponownie odwraca kierunek, przywracając kierunek pierwotny.

IOI-kun chce ustalić pierwotny kierunek każdego przenośnika, wykonując powyższą sekwencję operacji co najwyżej 30 razy.

Napisz program, który na podstawie informacji o stołach połączonych przenośnikami realizuje strategię IOI-kuna ustalającą pierwotny kierunek każdego przenośnika za pomocą co najwyżej 30 wykonań powyższej sekwencji operacji.

Szczegóły implementacji

Należy zgłosić jeden plik.

Jest to plik conveyor.cpp. Powinien implementować poniższą funkcję. Program powinien dołączyć conveyor.h za pomocą dyrektywy preprocesora #include.

W pliku conveyor.cpp należy zaimplementować następującą funkcję.

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

Ta funkcja jest wywoływana dokładnie raz dla każdego przypadku testowego.

• Parametr N oznacza liczbę stołów $N$.
• Parametry A, B są tablicami długości $N-1$, opisującymi stoły połączone przenośnikami.

Twój program może wywoływać następujące funkcje.

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

Za pomocą tej funkcji IOI-kun wykonuje operacje w fabryce.

• Parametr x jest tablicą długości $N-1$. Dla $0\le i\le N-2$ IOI-kun odwraca kierunek przenośnika $i$, jeśli x[i] = 1, a nie odwraca go, jeśli x[i] = 0.
• Parametr y jest tablicą długości $N$. Dla $0\le j\le N-1$ IOI-kun kładzie produkt na stole $j$, jeśli y[j] = 1, a nie kładzie go, jeśli y[j] = 0.
• Niech z będzie wartością zwracaną przez tę funkcję. Jest to tablica długości $N$. Dla $0\le j\le N-1$ na stole $j$ znajduje się co najmniej jeden produkt, jeśli z[j] = 1, a nie ma na nim żadnego produktu, jeśli z[j] = 0.
• Długość tablicy x powinna wynosić $N-1$. Jeśli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [1].
• Każdy element tablicy x powinien być równy $0$ lub $1$. Jeśli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [2].
• Długość tablicy y powinna wynosić $N$. Jeśli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [3].
• Każdy element tablicy y powinien być równy $0$ lub $1$. Jeśli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [4].
• Funkcji Query nie wolno wywołać więcej niż 30 razy. Jeśli zostanie wywołana więcej niż 30 razy, program otrzyma werdykt Wrong Answer [5].

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

Za pomocą tej funkcji IOI-kun zgłasza pierwotny kierunek każdego przenośnika.

• Parametr a jest tablicą długości $N-1$. Dla $0\le i\le N-2$ przenośnik $i$ transportuje produkty z $A_i$ do $B_i$, jeśli a[i] = 0, a z $B_i$ do $A_i$, jeśli a[i] = 1.
• Długość tablicy a powinna wynosić $N-1$. Jeśli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [6].
• Każdy element tablicy a powinien być równy $0$ lub $1$. Jeśli ten warunek nie jest spełniony, program otrzyma werdykt Wrong Answer [7].
• Jeśli IOI-kun zgłosi błędny kierunek któregoś przenośnika, program otrzyma werdykt Wrong Answer [8].
• Funkcję Answer należy wywołać dokładnie raz. Jeśli zostanie wywołana więcej niż raz, program otrzyma werdykt Wrong Answer [9]. Jeśli po zakończeniu funkcji Solve okaże się, że funkcja Answer nie została wywołana, program otrzyma werdykt Wrong Answer [10].

Ważne uwagi

• Program może implementować inne funkcje do użytku wewnętrznego oraz używać zmiennych globalnych.
• Program nie może korzystać ze standardowego wejścia ani standardowego wyjścia. Nie może też w żaden sposób komunikować się z innymi plikami. Może jednak wypisywać informacje diagnostyczne na standardowe wyjście błędów.

Kompilacja i uruchamianie testów

Ze strony konkursu można pobrać archiwum zawierające przykładowy program oceniający, który umożliwia testowanie programu. Archiwum zawiera również przykładowy plik źródłowy twojego programu.

Przykładowy program oceniający znajduje się w pliku grader.cpp. Aby przetestować program, umieść pliki grader.cpp, conveyor.cpp i conveyor.h w tym samym katalogu i skompiluj je poniższym poleceniem. Zamiast tego możesz uruchomić skrypt compile.sh zawarty w archiwum.

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

Po pomyślnej kompilacji powstanie plik wykonywalny grader.

Pamiętaj, że właściwy program oceniający różni się od przykładowego. Przykładowy program oceniający działa jako pojedynczy proces, odczytuje dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście.

Wejście przykładowego programu oceniającego

Przykładowy program oceniający odczytuje ze standardowego wejścia następujące dane.

$$ \begin{gathered} N\\ A_0\quad A_1\quad\cdots\quad A_{N-2}\\ B_0\quad B_1\quad\cdots\quad B_{N-2}\\ C_0\quad C_1\quad\cdots\quad C_{N-2} \end{gathered} $$

Dla $0\le i\le N-2$ mamy $C_i=0$, jeśli przenośnik $i$ transportuje produkty ze stołu $A_i$ na stół $B_i$. W przeciwnym razie $C_i=1$.

Wyjście przykładowego programu oceniającego

Przykładowy program oceniający wypisuje na standardowe wyjście poniższe informacje (cudzysłowy służą jedynie do wyróżnienia tekstu).

• Jeśli program zostanie uznany za poprawny, liczba wywołań funkcji Query zostanie podana w postaci „Accepted: 22”.
• Jeśli program otrzyma dowolny rodzaj werdyktu błędnej odpowiedzi, przykładowy program oceniający wypisze jego typ w postaci „Wrong Answer [4]”.

Jeśli program spełnia warunki kilku rodzajów błędnej odpowiedzi, przykładowy program oceniający zgłosi tylko jeden z nich.

W przykładowym programie oceniającym spośród przenośników transportujących produkty ze stołu, na którym umieszczono produkt, przenośnik transportujący ten produkt wybierany jest jednostajnie losowo za pomocą liczb pseudolosowych, których wyniki nie zmieniają się między uruchomieniami. Aby zmienić ziarno generatora liczb pseudolosowych, uruchom przykładowy program oceniający, podając jako pierwszy argument liczbę całkowitą, jak poniżej.

./grader 2023

Uwagi dotyczące oceniania

W niektórych przypadkach testowych właściwy program oceniający jest adaptacyjny. Oznacza to, że początkowo nie ma ustalonej odpowiedzi i odpowiada w zależności od wcześniejszych wywołań funkcji Query. Gwarantuje się, że istnieje co najmniej jedna odpowiedź zgodna ze wszystkimi odpowiedziami programu oceniającego.

Ograniczenia

Wszystkie dane wejściowe spełniają poniższe warunki.

• $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$).
• Jeśli pominiemy kierunki przenośników, każda para stołów jest połączona pewnym ciągiem przenośników.

Podzadania

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

Przykład

Poniżej przedstawiono przykładowe wejście dla przykładowego programu oceniającego oraz odpowiadające mu wywołania funkcji.

Wejście 1

3
0 2
2 1
1 0

Wywołania funkcji

Solve(3, [0, 2], [2, 1])

Dla pierwszego wywołania funkcji Query inną możliwą wartością zwracaną, oprócz [1, 0, 0], jest [0, 1, 0].

Dla drugiego wywołania funkcji Query produkt ze stołu $0$ jest transportowany na stół $2$ przez przenośnik $0$ i tam się zatrzymuje. Pamiętaj, że nie zostanie on następnie przetransportowany na stół $1$ przez przenośnik $1$.

Pamiętaj, że to przykładowe wejście nie spełnia ograniczeń żadnego podzadania.

Spośród plików dostępnych na stronie konkursu sample-02.txt spełnia ograniczenia podzadania 1, a sample-03.txt spełnia ograniczenia podzadania 2.