To zadanie komunikacyjne. Uwaga: w tym zadaniu dozwolony jest wyłącznie język C++.

Takina i Chisato są na konwencie owoców. Po dniu robienia zdjęć swoim ulubionym cosplayerom owoców, natknęły się na stoisko z grą.

Zasady gry są następujące: Istnieje $n$ owoców, każdy z unikalną etykietą od $1$ do $n$. Dokładnie jeden z owoców jest cytryną, ale ani Takina, ani Chisato nie wiedzą jeszcze, który to. * Takina otrzyma wszystkie $n$ owoców jeden po drugim. Jej celem jest przekazanie etykiety cytryny Chisato (która w trakcie tego procesu ma zawiązane oczy).

Przed otrzymaniem jakichkolwiek owoców, Takina otrzymuje tablicę $p$, która reprezentuje kolejność, w jakiej pojawią się etykiety owoców. $p[1]$ będzie etykietą pierwszego owocu, $p[2]$ etykietą drugiego owocu i tak dalej. Następnie Takina zapisze ciąg binarny $b$ zawierający tylko $0$ i $1$. Ciąg nie może być dłuższy niż $5000$ znaków, ale może być pusty. Niech $x$ oznacza długość $b$.

Następnie owoce są podawane Takinie jeden po drugim we wspomnianej kolejności. Po otrzymaniu każdego owocu Takina jest informowana, czy jest on cytryną. Jeśli owoc nie jest cytryną, Takina może zdecydować, czy go zjeść, czy nie. Decyzja ta musi zostać podjęta przed otrzymaniem następnego owocu i nie może zostać zmieniona. Jeśli owoc jest cytryną, Takina nie może go zjeść.

Niech $y$ oznacza całkowitą liczbę owoców zjedzonych przez Takinę.

Na koniec Chisato otrzymuje ciąg $b$ oraz posortowaną listę etykiet owoców, które nie zostały zjedzone. Korzystając z tych informacji, Chisato musi określić etykietę owocu, który jest cytryną.

Takina i Chisato zdecydowały się zagrać w tę grę $t$ razy. Zaprojektuj strategię, aby poprawnie zidentyfikować cytrynę, minimalizując jednocześnie $x$ oraz $y$.

Szczegóły implementacji

To zadanie komunikacyjne. Nie czytaj ze standardowego wejścia ani nie pisz na standardowe wyjście.

Musisz zaimplementować trzy procedury.

Dla Takiny należy zaimplementować:

std::string init(int subtask, int n, std::vector<int> p)

• subtask: indeks podzadania, do którego należy przypadek testowy.
• n: liczba owoców.
• p: tablica o długości $n + 1$, gdzie:
  • $p[0] = 0$, oraz
  • dla każdego $1 \le i \le n$, $p[i]$ to etykieta $i$-tego owocu, który zostanie podany Takinie.
• Ta procedura jest wywoływana $t$ razy na przypadek testowy, raz na początku każdej gry.

Ta procedura powinna zwrócić ciąg $b$ o długości od $0$ do $5000$ włącznie, składający się wyłącznie z $0$ i $1$. Jeśli zostanie zwrócony ciąg o nieprawidłowej długości lub formacie, otrzymasz werdykt Wrong Answer.

bool receive_fruit(int id, bool is_lemon)

• id: etykieta owocu podanego Takinie.
• is_lemon: true, jeśli podany owoc jest cytryną, w przeciwnym razie false.
• Ta procedura jest wywoływana $n$ razy dla każdej z $t$ gier, raz dla każdego owocu.

Ta procedura powinna zwrócić true, jeśli owoc powinien zostać zjedzony, a w przeciwnym razie false. Jeśli zostanie zwrócone true, gdy is_lemon wynosi true, otrzymasz werdykt Wrong Answer.

Dla Chisato należy zaimplementować:

int answer(int subtask, int n, std::string b, std::vector<int> uneaten)

• subtask: indeks podzadania, do którego należy przypadek testowy.
• n: liczba owoców.
• b: ciąg zwrócony przez init.
• uneaten: posortowany wektor o długości $n - y + 1$ zawierający etykiety owoców niezjedzonych przez Takinę, gdzie:
  • uneaten[0] = 0, oraz
  • uneaten[i] to $i$-ta najmniejsza etykieta wśród niezjedzonych owoców.
• Ta procedura jest wywoływana $t$ razy na przypadek testowy, raz na końcu każdej gry.

Ta procedura powinna zwrócić liczbę całkowitą, etykietę cytryny. Jeśli zwracana wartość nie pasuje do poprawnej etykiety, otrzymasz werdykt Wrong Answer.

Właściwe sprawdzanie polega na dwukrotnym uruchomieniu programu wywołującego powyższe procedury:

1. W pierwszym uruchomieniu następujące kroki są wykonywane $t$ razy:
   • init jest wywoływane raz.
   • receive_fruit jest wywoływane $n$ razy, zgodnie z kolejnością owoców podanych Takinie.
   • Twój program może przechowywać i zachowywać informacje między kolejnymi wywołaniami.
2. W drugim uruchomieniu kolejność gier może być inna niż w pierwszym uruchomieniu. Dla każdej z $t$ gier:
   • answer jest wywoływane raz. Poza parametrami przekazanymi do answer, Twój program nie może uzyskiwać dostępu do informacji z pierwszego uruchomienia.

Ponieważ procedura może być wywołana więcej niż raz, należy zwrócić uwagę na wpływ pozostałych danych z poprzedniego wywołania na bieżące wywołanie.

Ograniczenia

Dla wszystkich przypadków testowych dane wejściowe spełniają następujące warunki: $1 \le t \le 10\,000$ $n = 500$ $1 \le p[i] \le n$ dla wszystkich $1 \le i \le n$ Istnieje dokładnie jedna cytryna.

Dla każdego podzadania Twój program będzie oceniany inaczej w zależności od długości ciągu zapisanego przez Takinę ($x$) oraz liczby owoców, które zje ($y$). Twój wynik dla każdego przypadku testowego jest obliczany przy użyciu maksymalnej wartości $x$ we wszystkich $t$ grach oraz maksymalnej wartości $y$ we wszystkich $t$ grach.

Przykład

Wejście 1

(input data)

Wyjście 1

(output data)

Uwagi

W tym przykładzie Takina zjada owoce o etykietach 3 i 2, więc niezjedzone owoce to $\{1, 4\}$. Wektor uneaten przekazany do answer to zatem [0, 1, 4]. Używając b i uneaten, procedura answer zwraca 4, co jest etykietą cytryny. Ta strategia pozwoliła poprawnie zidentyfikować cytrynę przy $x = 3$ i $y = 2$.

Testing

Możesz pobrać przykładowy grader (grader.cpp), plik nagłówkowy (lemon.h) oraz szablon rozwiązania (lemon.cpp) w sekcji załączników. Do testowania udostępniono dwa pliki wejściowe: sample1.txt oraz sample2.txt. Do kompilacji i uruchomienia rozwiązania w celu testów możesz użyć skryptów compile.sh oraz run.sh.

Testy użytkownika CMS nie są wspierane w tym zadaniu.

Sample Grader

Przykładowy grader jest dostarczony, aby pomóc w lokalnym testowaniu implementacji. W przeciwieństwie do oficjalnego gradera, przykładowy grader uruchamia Twój program tylko raz i nie zmienia kolejności testów dla Takiny i Chisato.

Input Format

Pierwsza linia wejścia zawiera jedną liczbę całkowitą subtask. Druga linia wejścia zawiera jedną liczbę całkowitą t. Kolejne $t$ linii wejścia opisuje każdą grę. Każda gra jest opisana przez: linię zawierającą dwie liczby całkowite $n$ oraz $l$, reprezentujące liczbę owoców oraz etykietę cytryny, oraz linię zawierającą $n$ liczb całkowitych $p[1], p[2], \dots, p[n]$.

Output Format

Przykładowy grader wypisuje pojedynczą liczbę rzeczywistą reprezentującą ułamek wyniku obliczony na podstawie wartości $x$ oraz $y$ we wszystkich grach.

Note

Dodatkowe komunikaty diagnostyczne mogą być wypisywane na standardowe wyjście błędów. Przykładowy grader nie symuluje zachowania oficjalnego gradera.