Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 1024 MB 満点: 100 難易度: [表示] インタラクティブ ハック可能 ✓
統計

Descripción

Por supuesto, esto es un problema.

Este es un problema interactivo. Se te da un grafo no dirigido desconocido con $n$ vértices y $m$ aristas, sin aristas múltiples ni bucles. Cada vez, puedes hacer la siguiente pregunta a la biblioteca de interacción:

  • Dado un conjunto de vértices $S \subseteq \{1, 2, \dots, n\}$, preguntar si este conjunto de vértices es un conjunto independiente.

Aquí, un conjunto independiente significa que no hay ninguna arista entre dos vértices distintos cualesquiera en el conjunto $S$.

Tu objetivo es determinar todo el conjunto de aristas del grafo utilizando no más de $M = n + m(2 + \lceil\log_2 n\rceil)$ consultas.

Ten en cuenta que no conoces el valor de $m$ de antemano, y la biblioteca de interacción es adaptativa, es decir, el grafo no está fijo desde el principio, sino que se ajustará dinámicamente según tus consultas.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 100$), que denota el número de casos de prueba.

Para cada caso de prueba, una línea contiene un entero $n$ ($1 \le n \le 500$), que denota el número de vértices del grafo no dirigido desconocido.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $500$, $0 \le m \le 500$, y la suma de $m$ no supera $500$.

Interacción

Cuando necesites hacer una consulta, imprime una línea:

? k v_1 v_2 ... v_k

donde $k$ denota el tamaño del conjunto de vértices, y $v_1, v_2, \dots, v_k$ son los índices de los vértices en el conjunto que estás consultando, todos distintos entre sí.

La biblioteca de interacción devolverá un entero: $1$ si el conjunto de vértices es un conjunto independiente; $0$ en caso contrario.

Cuando hayas determinado todas las aristas del grafo, imprime una línea:

! m u_1 v_1 u_2 v_2 ... u_m v_m

donde $m$ es el número de aristas en el grafo no dirigido, y $(u_i, v_i)$ representa una arista en el grafo. Puedes imprimir las aristas en cualquier orden.

Después de eso, si no quedan casos de prueba, tu programa debe terminar inmediatamente; de lo contrario, debe proceder al siguiente caso de prueba.

Ejemplos

Entrada 1

1
4
0
1
0
0
1
0

Salida 1

? 2 1 2
? 2 1 3
? 2 1 4
? 2 2 3
? 2 2 4
? 2 3 4
! 4 1 2 2 3 3 4 1 4

Nota

El ejemplo demuestra un proceso interactivo en el que se consulta individualmente si existe cada arista.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1842EditorialOpenNew Editorial for Problem #18123wangmaruiView

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.