To jest zadanie interaktywne.

Treść zadania

Wciągnąłeś się w grę logiczną. W tym etapie gry Twoim zadaniem jest otwarcie skrzyni ze skarbami.

Masz do dyspozycji $n$ kluczy o numerach od $0$ do $n-1$ oraz $n$ zamków na skrzyni, również ponumerowanych od $0$ do $n-1$. Twoim zadaniem jest zebranie wskazówek, umieszczenie kluczy w zamkach w odpowiedniej kolejności, a następnie naciśnięcie przełącznika, aby otworzyć skrzynię. Tę poprawną kolejność kluczy można przedstawić jako permutację $p$ długości $n$ (indeksowaną od $0$), gdzie $p_i$ oznacza numer klucza, który powinien znaleźć się w zamku o numerze $i$.

Twoja próba polega na podaniu permutacji $q$ długości $n$, co oznacza umieszczenie klucza o numerze $q_i$ w zamku o numerze $i$. Jeśli dla każdego $0 \le i \le n-1$ zachodzi $p_i=q_i$, oznacza to, że Twoja próba jest poprawna, skrzynia się otwiera i przechodzisz poziom. W przeciwnym razie próba kończy się niepowodzeniem. Masz tylko jedną szansę na otwarcie skrzyni, więc musisz być niezwykle ostrożny.

Po dokładnej obserwacji odkryłeś tajemnicę skrzyni: z tyłu znajduje się ukryty przycisk. Po podaniu permutacji $q$ i umieszczeniu kluczy w zamkach, możesz nacisnąć ukryty przycisk, a skrzynia poda informację, ile kluczy znajduje się na poprawnych pozycjach – czyli ile jest takich $i$ ($0 \le i \le n-1$), że $p_i=q_i$. Tę operację nazywamy zapytaniem. Możesz zmieniać permutację $q$ i wykonywać zapytania wielokrotnie, zanim naciśniesz ostateczny przełącznik, aż zbierzesz wystarczająco dużo informacji, aby ustalić poprawną permutację $p$.

Ze względu na poziom trudności i atrakcyjność gry istnieje specjalna zasada: liczba zapytań do skrzyni nie może przekroczyć $20000$. Po przekroczeniu tego limitu skrzynia zostanie trwale zablokowana, co oznacza przegraną. Sukces w grze zależy od Twoich umiejętności!

Szczegóły implementacji

Nie musisz i nie powinieneś implementować funkcji main. Na początku swojego programu powinieneś dodać #include "puzzle.h" i zaimplementować następującą funkcję:

void play(int n);

• $n$ oznacza długość permutacji.
• Podczas działania biblioteki interaktywnej funkcja ta zostanie wywołana dokładnie raz.

Możesz wywołać następujące dwie funkcje:

int query(const std::vector<int> &q);

• $q$ powinno być permutacją długości $n$, co oznacza, że długość $q$ wynosi $n$, a wszystkie liczby całkowite od $0$ do $n-1$ występują w $q_0 \sim q_{n-1}$ dokładnie raz.
• Funkcja porówna podaną przez Ciebie permutację $q$ z permutacją docelową $p$ i zwróci wynik zapytania, czyli liczbę takich $i$ ($0 \leq i \leq n-1$), że $p_i = q_i$.
• Liczba wywołań tej funkcji nie powinna przekroczyć $20000$.

void check(const std::vector<int> &q);

• $q$ powinno być permutacją długości $n$, co oznacza, że rozmiar $q$ wynosi $n$, a wszystkie liczby całkowite od $0$ do $n-1$ występują w $q_0 \sim q_{n-1}$ dokładnie raz.
• Ta funkcja powinna zostać wywołana dokładnie raz podczas wykonywania Twojej funkcji play.
• Funkcja porówna podaną przez Ciebie permutację $q$ z permutacją docelową $p$. Jeśli $p=q$, uznaje się, że Twoja odpowiedź jest poprawna, w przeciwnym razie uznaje się ją za błędną.
• Niezależnie od wyniku, biblioteka interaktywna wypisze odpowiedni komunikat i natychmiast zakończy działanie po wykonaniu tej funkcji.

Musisz zagwarantować, że parametry przekazywane do funkcji query lub check spełniają powyższe wymagania.

Możesz zapoznać się z dostarczoną biblioteką referencyjną, aby poznać więcej szczegółów implementacji.

Testowanie programu

W dostarczonych plikach znajduje się referencyjna implementacja biblioteki interaktywnej grader.cpp. Implementacja używana podczas testów końcowych różni się od tej dostarczonej, dlatego rozwiązanie zawodnika nie powinno polegać na szczegółach implementacji biblioteki.

Zakładając, że Twój plik źródłowy nazywa się puzzle.cpp, umieść dostarczone pliki w tym samym katalogu i skompiluj program za pomocą następującego polecenia:

g++ grader.cpp puzzle.cpp -o puzzle -O2 -std=c++14 -lm

Podczas uruchamiania skompilowanego pliku wykonywalnego:

• Program wczytuje ze standardowego wejścia dane w następującym formacie:

  • Pierwsza linia: liczba całkowita $n$, oznaczająca długość permutacji. Musisz zapewnić $2 \leq n \leq 1000$;
  • Druga linia: $n$ liczb całkowitych $p_0, p_1, \dots, p_{n-1}$, oznaczających permutację docelową. Musisz zapewnić, że $p_0, \dots, p_{n-1}$ jest permutacją długości $n$, czyli wszystkie liczby od $0$ do $n-1$ występują dokładnie raz.

• Po wczytaniu danych biblioteka przeprowadzi testy i wypisze:

  • Jeśli program działa poprawnie, liczba wywołań query nie przekracza $20000$, a w funkcji check przekazano poprawną permutację, wypisane zostanie:

    Correct.
    cnt = x

    gdzie $x$ to liczba wywołań funkcji query.

  • W przeciwnym razie wypisany zostanie odpowiedni komunikat o błędzie.

Przykład

Wejście 1

3
1 0 2

Wyjście 1

Correct.
cnt = 3

Uwagi

Powyżej przedstawiono przykładowe wyjście uzyskane przy użyciu dostarczonego grader.cpp i poprawnego programu.

Dla tego przykładu możliwy ciąg wywołań to:

• Wywołanie query([0, 1, 2]), zwraca $1$;
• Wywołanie query([0, 2, 1]), zwraca $0$;
• Wywołanie query([1, 0, 2]), zwraca $3$;
• Wywołanie check([1, 0, 2]).

Podzadania

Zadanie jest oceniane w systemie pakietowym. Wynik za każde podzadanie jest równy minimalnej liczbie punktów uzyskanej za testy wchodzące w jego skład.

Dla wszystkich testów $1 \leq n \leq 1000$.

Dla pierwszych 6 podzadań, jeśli program działa poprawnie, liczba wywołań query nie przekracza $20000$, a w funkcji check przekazano poprawną permutację, otrzymasz pełną liczbę punktów za dany test.

Dla 7. podzadania, oprócz powyższych warunków, możesz otrzymać punkty częściowe. Niech $m$ oznacza liczbę wywołań query. Twój wynik oblicza się następująco:

Uwagi

Gwarantuje się, że dla każdego poprawnego zestawu danych i wywołań w ramach limitów, czas działania samej biblioteki interaktywnej nie przekroczy $0.2\text{s}$, a zużycie pamięci nie przekroczy $128\text{MiB}$.

Nagłówki wymagane do poprawnego działania biblioteki są już zawarte w dostarczonym pliku referencyjnym; Twój program może zawierać dowolne potrzebne Ci nagłówki.

Biblioteka interaktywna w tym zadaniu nie jest adaptacyjna, co oznacza, że permutacja docelowa jest ustalona przed wywołaniem funkcji play i nie zmienia się w zależności od Twoich zapytań.

Próby uzyskania punktów poprzez dostęp do plików wejściowych/wyjściowych, ataki na system oceniania lub biblioteki testujące są traktowane jako oszustwo, a uzyskane w ten sposób punkty są nieważne.