oj.uz

Submission #860947

# Submission time Handle Problem Language Result Execution time Memory
860947 2023-10-14T21:56:59 Z BlancaHM Carnival (CEOI14_carnival) C++14
100 / 100
 5 ms 596 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 3 ms 344 KB Output is correct
7 Correct 5 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 3 ms 344 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 436 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 436 KB Output is correct
7 Correct 3 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 3 ms 428 KB Output is correct
5 Correct 3 ms 436 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 2 ms 436 KB Output is correct