Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 تفاعلية
الإحصائيات

Descripción

Hay un grafo dirigido de $n$ vértices numerados del $1$ al $n$. Para cada vértice $1 \le i \le n$, el grado de salida del vértice $i$ es a lo sumo uno; por lo tanto, podemos describir el grafo mediante un arreglo $p_i$, donde $p_i = 0$ si el grado de salida del vértice $i$ es cero, y en caso contrario $1 \le p_i \le n$, $p_i \ne i$, y existe una arista dirigida de $i$ a $p_i$. No hay ciclos dirigidos en el grafo, por lo que desde cualquier vértice $i$, el camino formado al avanzar repetidamente al siguiente vértice a lo largo de las aristas dirigidas terminará finalmente en un vértice con grado de salida cero.

Inicialmente, hay una ficha de madera en uno de los vértices. Cuando das una palmada, si la ficha está en un vértice $i$ con $p_i$ distinto de cero, se moverá al vértice $p_i$; de lo contrario, no se mueve. Sin embargo, no puedes ver dónde está la ficha en absoluto: la única operación que puedes realizar es elegir un subconjunto de vértices, colocar la ficha en uno de los vértices elegidos, dar palmadas un cierto número de veces y observar si la ficha termina en uno de los vértices elegidos. Incluso la posición inicial de la ficha y el número de veces que das palmadas son elegidos por el interactor: tú solo puedes elegir el subconjunto de vértices y observar el número máximo de veces que puedes dar palmadas de modo que la ficha pueda comenzar en uno de tus vértices elegidos y terminar en uno de tus vértices elegidos.

Te gustaría añadir una única arista de $x$ a $y$ ($1 \le x, y \le n$, $x \ne y$, y $p_x = 0$, es decir, puedes asignar $p_x = y$), de manera que puedas dar palmadas aún más veces en todo el grafo que antes. Aun así, añadir la arista no puede crear ningún ciclo dirigido en el grafo.

Encuentra cualquier arista de este tipo que puedas añadir consultando el número máximo de veces que puedes dar palmadas en a lo sumo $n$ subconjuntos de vértices, o determina que es imposible añadir dicha arista.

Entrada

La primera línea de la entrada contiene un único entero $n$ ($1 \le n \le 1000$).

Interacción

Para hacer una consulta, imprime una sola línea de la forma $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, donde $1 \le k \le n$, y $1 \le u_i \le n$ son vértices distintos dos a dos en tu subconjunto elegido. Luego lee una sola línea que contiene un único entero: el número máximo de veces que puedes dar palmadas de modo que la ficha pueda comenzar en uno de tus vértices elegidos y terminar en uno de tus vértices elegidos. Puedes hacer a lo sumo $n$ consultas.

Después de haber determinado la arista que deseas añadir, imprime una sola línea de la forma $\texttt{! } x \text{ } y$, donde $1 \le x, y \le n$ son los extremos de la arista dirigida que deseas añadir. Si hay múltiples soluciones, puedes imprimir cualquiera de ellas.

Si es imposible añadir dicha arista, imprime $-1 \text{ -1}$ en lugar de los extremos de la arista.

Tu solución debe terminar inmediatamente después de imprimir la respuesta.

Vacía el búfer de salida (flush) después de cada consulta que realices.

El interactor no es adaptativo; el grafo está fijado de antemano.

Ejemplo

6

2

1

2
? 4 1 2 3 4

? 2 5 6

? 3 4 5 6

! 5 1

Nota

problem_17169_c1d82052e4ed01f4f4f5920c82dcbcb1.png

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1220EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.