To zadanie jest interaktywne.
W przeddzień otwarcia festiwalu deserów szef kuchni starannie dopracowuje popisowy deser swojej cukierni — „千层幻彩慕斯”. Deser składa się z $n$ kawałków musu o różnych smakach, ponumerowanych kolejno $0,1,\dots,n-1$.
Jednak w zamieszaniu pomocnik przypadkowo pomylił kolejność kawałków musu. Teraz są one ustawione w jednym rzędzie od lewej do prawej, tworząc nieznaną permutację położeń $p=(p_0,p_1,\dots,p_{n-1})$, gdzie $p_i$ oznacza numer kawałka musu znajdującego się na pozycji $i$.
Aby ustalić dokładne położenie każdego kawałka musu, możesz korzystać z urządzenia do badania deserów. Za każdym razem wybierasz trzy parami różne pozycje $x,y,z$, a urządzenie zwraca sumę najmniejszego i największego numeru spośród tych trzech kawałków musu:
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
Już wkrótce rozlegnie się dzwon oznajmiający otwarcie. Czy potrafisz za pomocą ograniczonej liczby badań dokładnie odtworzyć rzeczywiste położenie każdego kawałka musu?
Dana jest permutacja $p$ długości $n$, której elementami są dokładnie $0,1,\ldots,n-1$. Nie znasz zawartości $p$.
Możesz wybrać trzy parami różne indeksy $x,y,z$, a biblioteka interaktywna zwróci
$$ \min(p_x,p_y,p_z)+\max(p_x,p_y,p_z). $$
Twoim zadaniem jest odtworzenie całej permutacji. Limit liczby zapytań oraz sposób obliczania wyniku na podstawie liczby zapytań opisano poniżej.
Szczegóły implementacji
Nie musisz i nie powinieneś implementować funkcji main. Przesyłany plik źródłowy powinien zawierać:
#include "mousse.h"Należy zaimplementować następujące dwie funkcje:
void init(int c);
std::vector<int> mousse(int c, int n);- $c$ jest numerem podzadania; $c=0$ oznacza przykład. Każdy test zawiera dokładnie jedną instancję zadania. Biblioteka interaktywna wywołuje dla tego testu raz
init(c), a następnie razmousse(c,n). moussepowinno zwrócić tablicę długości $n$, w której element o indeksie $i$ jest równy $p_i$. Indeksy zaczynają się od $0$.
Aby wykonać jedno zapytanie, możesz wywołać następującą funkcję:
int query(int x, int y, int z);Musi zachodzić $0\le x,y,z < n$, a $x,y,z$ muszą być parami różne. Funkcja zwraca $\min(p_x,p_y,p_z)+\max(p_x,p_y,p_z)$.
Testowanie programu
Załączniki zawierają mousse.h, lokalną bibliotekę interaktywną grader.cpp oraz przykładowy program template_mousse.cpp. Zapisz swój program jako mousse.cpp; w katalogu tego zadania możesz uruchomić:
g++ grader.cpp mousse.cpp -o mousse -O2 -std=c++14
./mousse < mousse1.inLokalna biblioteka interaktywna odczytuje ukrytą permutację ze standardowego wejścia. Program uczestnika nie może samodzielnie odczytywać tych danych. Format wejścia jest następujący:
- Pierwszy wiersz zawiera dwie liczby całkowite $c,n$.
- Drugi wiersz zawiera $p_0,p_1,\ldots,p_{n-1}$.
Jeśli odpowiedź jest poprawna, biblioteka interaktywna wypisuje Correct! oraz Max queries used: Q, gdzie $Q$ jest liczbą zapytań wykonanych w tym teście. Jeśli odpowiedź jest błędna, wypisuje Wrong answer.. W przypadku niedozwolonego zapytania lub przekroczenia limitu liczby zapytań program wypisuje komunikat o błędzie na standardowy strumień błędów i kończy działanie. Możesz dodać argument -v, aby zobaczyć liczbę zapytań wykonanych w tym teście.
Przykład
Wejście 1
0 10
0 2 9 1 5 8 3 7 6 4Wyjście 1
Correct!
Max queries used: 15Uwagi
Na przykład po wywołaniu query(0,1,2) trzy odpowiadające wartości to $0,2,9$, więc funkcja zwraca $0+9=9$. Program wzorcowy wykonuje dla tych danych $15$ zapytań. Przy zastosowaniu innej strategii liczba ta może być inna.
Ograniczenia
Dla wszystkich danych testowych $n\in\{10,100,10^5\}$, a $p$ jest permutacją liczb $0\sim n-1$. Każdy test zawiera dokładnie jedną instancję zadania.
| Numer podzadania | Punkty | $n =$ | $Q_{\max} = $ | Dodatkowa własność |
|---|---|---|---|---|
| $1$ | $5$ | $10$ | $1000$ | Brak |
| $2$ | $5$ | $100$ | $10000$ | Brak |
| $3$ | $30$ | $10^5$ | $2\times10^6$ | $p_0=0$ |
| $4$ | $60$ | $10^5$ | $2\times10^6$ | Brak |
Dla przykładu $c=0$, $n=10$, a limit liczby zapytań wynosi $1000$.
Podzadania
Uwaga:
- Biblioteka interaktywna nie jest adaptacyjna. Permutacja dla każdego testu jest ustalona przed wywołaniem programu uczestnika i nie zmienia się w zależności od zapytań.
- Nie wolno uzyskiwać ukrytej permutacji przez odczytywanie standardowego wejścia ani w żaden inny niedozwolony sposób. Implementacja biblioteki interaktywnej używanej podczas ostatecznej oceny może różnić się od implementacji biblioteki lokalnej.
Jeżeli w pewnym teście mousse zwróci błędną odpowiedź, argumenty query będą nieprawidłowe lub liczba zapytań przekroczy $Q_{\max}$ dla danego podzadania, mnożnik wyniku dla tego testu wyniesie $0$.
W podzadaniach $1,2$ pełną liczbę punktów za podzadanie można otrzymać tylko wtedy, gdy odpowiedzi we wszystkich testach są poprawne.
W podzadaniach $3,4$, jeśli mnożnik wyniku w którymkolwiek teście wynosi $0$, za całe podzadanie otrzymuje się $0$ punktów. W przeciwnym razie niech $Q$ oznacza największą liczbę zapytań spośród wszystkich testów danego podzadania. Mnożnik wyniku $f(Q)$ jest określony przez poniższą tabelę:
| Liczba zapytań $Q_i$ | Mnożnik wyniku $f_i$ |
|---|---|
| $99970$ | $100\%$ |
| $99975$ | $98\%$ |
| $99981$ | $95\%$ |
| $99988$ | $90\%$ |
| $99996$ | $84\%$ |
| $100000$ | $80\%$ |
| $100010$ | $74\%$ |
| $100026$ | $66\%$ |
| $100051$ | $58\%$ |
| $100093$ | $52\%$ |
| $150000$ | $32\%$ |
| $200000$ | $20\%$ |
| $1660964$ | $8\%$ |
| $2000000$ | $5\%$ |
Jeśli $Q\le 99970$, to $f(Q)=100\%$. Jeśli $Q$ leży pomiędzy dwoma sąsiednimi wierszami tabeli $(Q_i,f_i)$ i $(Q_{i+1},f_{i+1})$, to:
$$ f(Q)=f_i+\frac{Q-Q_i}{Q_{i+1}-Q_i}(f_{i+1}-f_i). $$
Wynik za podzadanie $3$ wynosi $30f(Q)$, a za podzadanie $4$ wynosi $60f(Q)$. Ostateczny wynik jest zaokrąglany do $3$ miejsc po przecinku.
Limit czasu: $10\ \mathrm{s}$.
Limit pamięci: $512\ \mathrm{MiB}$.