Submission #860947

#	Time	Username	Problem	Language	Result	Execution time	Memory
860947		BlancaHM	Carnival (CEOI14_carnival)	C++14	100 / 100	5 ms	596 KiB

carnival

#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>
#include <set>
#include <algorithm>
using namespace std;

vector<int> resolver(int N) {
	// Realizamos una consulta inicial para averiguar C
	int C;
	cout << N;
	for (int i = 1; i <= N; i++)
		cout << " " << i;
	cout << '\n';
	cin >> C;

	// Si hay un unico disfraz, todos los invitados llevan el mismo
	if (C == 1) {
		return vector<int>(N, 1);
	}

	// Primero, realizamos un pase para encontrar a los capitanes
	vector<int> capitanes = {0};
	vector<int> capitanNodo(N, 0);
	int respuestaConsulta;
	for (int i = 1; i < N; i++) {
		if ((int) capitanes.size() == C) {
			// Ya los hemos encontrado a todos
			break;
		}
		// Realizamos una fiesta con todos los capitanes y el nuevo nodo
		cout << capitanes.size() + 1;
		for (int & capi: capitanes) {
			cout << ' ' << capi+1;
		}
		cout << ' ' << i+1 << '\n';
		cin >> respuestaConsulta;
		if (respuestaConsulta > (int) capitanes.size()) {
			// i es un capitan tambien => lo metemos en el conjunto
			capitanes.push_back(i);
			capitanNodo[i] = i;
		}
	}

	// Una vez encontrados los capitanes, averiguamos el disfraz del resto
	for (int i = 1; i < N; i++) {
		// Podemos saltarnos los capitanes, ya que lo que buscamos para cada nodo es
		// el capitan de su grupo
		if (capitanNodo[i] == i) {
			continue;
		}
		int lo = 0, hi = (int) capitanes.size() - 1;
		while (lo < hi) {
			int mid = lo + (hi-lo)/2;
			// Preguntamos por la primera mitad
			cout << mid - lo + 2;
			for (int j = lo; j <= mid; j++) {
				cout << ' ' << capitanes[j]+1;
			}
			cout << ' ' << i+1 << '\n';
			cin >> respuestaConsulta;
			if (respuestaConsulta == mid - lo + 1) {
				// coincide con alguno de los capitanes
				hi = mid;
			} else {
				// no coincide
				lo = mid+1;
			}
		}
		// su capitan es capitanes[lo], que coincide con hi al acabar la busqueda
		capitanNodo[i] = capitanes[lo];
	}

	// Asignamos los numeros de los disfraces a cada grupo
	vector<int> disfraces(N);
	int disfracesDescubiertos = 0;
	// Primero a los capitanes
	for (int & capi: capitanes) {
		disfracesDescubiertos++;
		disfraces[capi] = disfracesDescubiertos;
	}
	// Ahora al resto
	for (int i = 0; i < N; i++) {
		if (capitanNodo[i] != i) {
			disfraces[i] = disfraces[capitanNodo[i]];
		}
	}
	return disfraces;
}

int main() {
	int N;
	cin >> N;
	vector<int> disfraces = resolver(N);
	cout << '0';
	for (int & disfraz: disfraces) {
		cout << ' ' << disfraz;
	}
	cout << '\n';
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20