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,\dots ,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\le i\le n$ oraz $1\le j\le n$ oraz $i\ne 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$, $\dots$, $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\le a_i$ dla wszystkich $1\le i\le n$ i pozwalamy $b_k\ne a_k$ dla co najwyżej jednego $k$.

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

Ograniczenia i punktacja

Liczba zawodników $n$ spełnia warunki $2\le n\le 1500$. Niewzruszoność $a_i$ każdego zawodnika spełnia $1\le a_i\le 86400$, 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