To jest zadanie interaktywne.

Alice i Bob grają w grę polegającą na zgadywaniu liczb. Najpierw Alice wybiera $b\in\{0,1\}$, a Bob nie zna wartości $b$. Następnie Alice generuje permutację zbioru $\{0,1\}^{64}$ w następujący sposób:

• Jeśli $b=0$, to $P$ jest wybierane jednostajnie losowo ze wszystkich permutacji zbioru $\{0,1\}^{64}$.
• Jeśli $b=1$:
  • $f_1,f_2,f_3$ są wybierane niezależnie i jednostajnie losowo ze wszystkich funkcji $\{0,1\}^{32}\to\{0,1\}^{32}$.
  • Aby obliczyć $P(x)$, Alice najpierw dzieli $x$ na $x=x_0\circ x_1$, gdzie $x_0, x_1$ mają po 32 bity.
  • Alice wykonuje następujące obliczenia:
    • $x_2=x_0\oplus f_1(x_1)$
    • $x_3=x_1\oplus f_2(x_2)$
    • $x_4=x_2\oplus f_3(x_3)$
  • Alice zwraca $x_3\circ x_4$ jako wynik $P(x)$. Innymi słowy, $P(x_0\circ x_1)=x_3\circ x_4$, gdzie $x_3, x_4$ są zdefiniowane jak powyżej.

Łatwo zauważyć, że w obu przypadkach otrzymane $P$ jest poprawnie zdefiniowaną permutacją. Teraz Bob musi określić wartość $b$. Może on zadać Alice dwa rodzaje zapytań:

• Bob wybiera dowolne $x\in\{0,1\}^{64}$ i pyta o $P(x)$.
• Bob wybiera dowolne $x\in\{0,1\}^{64}$ i pyta o $P^{-1}(x)$.

Ponieważ Alice się spieszy, wymaga, aby Bob wykonał nie więcej niż $256$ zapytań. Bob nie radzi sobie jednak z problemami probabilistycznymi, więc prosi Cię o pomoc. Pomóż Bobowi zaprojektować algorytm, który poprawnie odgadnie $b$.

Interakcja

To zadanie wspiera tylko język c++. W przesyłanym pliku źródłowym należy dołączyć interaction.h (patrz pliki do pobrania). Funkcje interfejsu używane do interakcji są zdefiniowane następująco:

/**
 * @brief Queries P(x) or P^{-1}(x)
 * @param x The value to query
 * @param rev Set rev=0 to query P(x), rev=1 to query P^{-1}(x)
 * @return P(x) for rev=0, P^{-1}(x) for rev=1
 */
unsigned long long getperm(unsigned long long x,int rev);
/**
 * @brief Make no more than 256 calls to getperm, to guess b
 * @see getperm
 * @return The b you guesses
 */
int guessb();

Należy zaimplementować funkcję int guessb() w swoim pliku źródłowym. Powinna ona wykonać nie więcej niż $256$ zapytań poprzez wywołanie getperm i zwrócić $0/1$ jako wynik zgadywania $b$. W razie wątpliwości, plik permutation.cpp w materiałach do zadania zawiera przykładową implementację, którą można zmodyfikować.

Kompilacja i uruchomienie

Użyj:

g++ -o grader grader.cpp permutation.cpp

aby skompilować plik źródłowy wraz z biblioteką interakcyjną i otrzymać plik wykonywalny grader. permutation.cpp to nazwa Twojego lokalnego pliku źródłowego.

Następnie w systemach Linux/MacOS użyj:

./grader

a w systemie Windows:

grader.exe

Wejście

Każdy zestaw testowy zawiera wiele przypadków testowych.

Pierwsza linia zawiera liczbę całkowitą dodatnią $t$, oznaczającą liczbę zestawów danych.

Druga linia zawiera dwie 64-bitowe liczby całkowite bez znaku $s_0,s_1$ ($0\le s_0,s_1\le 2^{64}-1$), reprezentujące ziarno generatora liczb losowych używane przez grader.

To jest zadanie grader.cpp. Nie należy odczytywać żadnych danych ze standardowego wejścia w przesyłanym pliku źródłowym.

Wyjście

Dla każdego zestawu danych wypisz jedną linię. Jeśli wykonano więcej niż 256 zapytań, wypisz QLE. W przeciwnym razie, jeśli zgadnięta wartość $b$ jest poprawna, wypisz OK; jeśli jest błędna, wypisz WA.

To jest zadanie grader.cpp. Nie należy zapisywać żadnych danych na standardowe wyjście w przesyłanym pliku źródłowym.

Ograniczenia

Dla 20% testów $t=1$.

Dla kolejnych 20% testów $t=4$.

Dla pozostałych 60% testów $t=100$.

Gwarantujemy, że całkowity czas potrzebny grader.cpp na przetworzenie $25600$ zapytań nie przekracza 10 ms.

O reprezentacji ciągów binarnych za pomocą liczb całkowitych: Przyjmujemy, że najmniej znaczący bit liczby odpowiada pierwszemu znakowi binarnemu, a najbardziej znaczący bit odpowiada ostatniemu znakowi binarnemu. Zatem dla $x=x_0\circ x_1$, $x_0$ to 32 najmniej znaczące bity $x$, a $x_1$ to 32 najbardziej znaczące bity $x$. Na przykład dla x=0xFEDCBA9876543210 mamy x_0=0x76543210 oraz x_1=0xFEDCBA98. Analogicznie dla $x_3\circ x_4$.

Uwagi

Dostarczony plik grader.cpp służy jedynie jako przykład. Podczas sprawdzania na systemie sędziowskim użyjemy innego pliku grader.cpp (gwarantującego identyczną funkcjonalność interfejsu). Przesyłany plik źródłowy powinien korzystać wyłącznie z interfejsu dostarczonego w interaction.h i nie powinien próbować uzyskiwać dostępu do wewnętrznych struktur grader.cpp.