Problem B
Konkurs gapienia się

Konkurs gapienia się to klasyczna bitwa niewzruszoności, w której dwie osoby wpatrują się w siebie nawzajem, zachowując przy tym wyraz twarzy o zapewnionym spokoju. Celem jest utrzymanie kontaktu wzrokowego dłużej niż Twój przeciwnik. Konkurs kończy się, gdy jeden z uczestników złamie opanowanie, zazwyczaj odwracając wzrok, uśmiechając się, mówiąc lub chichocząc.

Jako trener krajowego konkursu gapienia się musisz określić stopień niewzruszoności każdego z $n$ członków swojej drużyny na nadchodzące światowe finały. Sportowiec o numerze $i$ może utrzymać kontakt wzrokowy przez dokładnie $a_ i$ sekund, ale te wartości są ci nieznane na początku. Na przykład, możesz mieć drużynę składającą się z $n=3$ członków:

Kiedy zawodnicy $i$ oraz $j$ rywalizują, konfrontacja trwa dokładnie $\min (a_ i, a_ j)$ sekund, w którym to momencie słabszy zawodnik łamie opanowanie i obaj zawodnicy w ciągu ułamka sekundy zaczynają się uśmiechać i chichotać. Na przykład, jeśli Anna rywalizuje z Esther, zawody trwają przez $431$ sekund. Co ważne, dla postronnego obserwatora faktyczny zwycięzca konfrontacji (w tym przypadku, Ester) jest niemożliwy do określenia, mierzalny jest jedynie czas trwania konkursu.

Twoim celem jest oszacowanie wartości $a_1,\ldots , a_ n$ przy użyciu jak najmniejszej liczby konkursów gapienia się. Oczywiście, siła najsilniejszego zawodnika nigdy nie może być określona, więc wolno ci niedoszacować jedno z $a_ i$.

Interakcja

To jest problem interaktywny. Interakcja rozpoczyna się od wczytania ze standardowego wejścia pojedynczego wiersza zawierającego liczbę całkowitą $n$. Następnie możesz zadawać pytania w postaci “? $i$ $j$” takie, że $1\leq i\leq n$ oraz $1\leq j\leq n$ oraz $i\neq j$. Odpowiedzią na zapytanie jest jedna liczba całkowita: wartość $\min (a_ i, a_ j)$. Interakcja kończy się wypisaniem na standardowe wyjście pojedynczego wiersza składającego się ze znaku !, po którym następuje $n$ oszacowań w postaci liczb całkowitych $b_1$, $\ldots $, $b_ n$, oddzielonych spacjami. To musi być Twój ostatni wiersz wyjścia.

Twoje zgłoszenie będzie uznane za poprawne, jeśli $b_ i=a_ i$ dla każdego zawodnika $i$ z wyjątkiem jednego, którego możesz nie docenić. Tak dokładniej, wymagamy $b_ i\leq a_ i$ dla wszystkich $1\leq i\leq n$ i pozwalamy $b_ k \neq a_ k$ dla co najwyżej jednego $k$.

Interaktor jest nieadaptacyjny, co oznacza, że $a_1,\ldots , a_ n$ są już określone przed rozpoczęciem interakcji.

Ograniczenia i punktacja

Liczba zawodników $n$ spełnia warunki $2\leq n\leq 1500$. Niewzruszoność $a_ i$ każdego zawodnika spełnia $1\leq a_ i\leq 86\, 400$, liczby są parami różne. Możesz użyć co najwyżej $3000$ zapytań; ostatni wiersz twojego wyjścia, czyli wiersz zaczynający się znakiem !, nie jest uznawany za zapytanie.

Twoje rozwiązanie zostanie przetestowane na zestawie grup testowych, z których każda warta jest pewną liczbę punktów. Każda grupa testowa zawiera zestaw przypadków testowych. Aby uzyskać punkty za grupę testową musisz rozwiązać wszystkie przypadki testowe w tej grupie. Twój ostateczny wynik będzie maksymalnym wynikiem pojedynczego zgłoszenia.

Dla grupy $3$, twój wynik to minimalny wynik wśród wszystkich przypadków testowych w grupie. Wynik dla każdego przypadku testowego zależy od liczby zapytań, których używasz; mniejsza liczba zapytań jest lepsza: Załóżmy, że używasz $q$ zapytań. Jeśli $q \le n+25$, to otrzymujesz pełne $80$ punktów. Jeśli $q > 3000$, to nie dostaniesz żadnych punktów. W przeciwnym razie otrzymujesz $118.2 - 12 \cdot \ln (q - n)$ punktów, zaokrąglone do najbliższej liczby całkowitej. Na przykład, dla $n = 1500$ oraz $q = 3000$ otrzymasz $30$ punktów.

Wyjaśnienie przykładowej interakcji

Przykładowa interakcja $1$ pokazuje możliwą interakcję z wykorzystaniem powyższego przykładu. Zauważ, że siły Anny i Tony’ego są poprawnie określone. (Siła Estera nigdy nie może być określona).

3

? 1 2

431

? 1 3

121

? 3 2

121

! 431 431 121