oj.uz

Submission #860944

# Submission time Handle Problem Language Result Execution time Memory
860944 2023-10-14T21:17:26 Z BlancaHM Carnival (CEOI14_carnival) C++14
100 / 100
 4 ms 596 KB 
#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>
#include <set>
#include <algorithm>
using namespace std;

// Usaremos la estructura de datos UFDS
vector<int> par; // Nos guardamos para cada nodo su padre
vector<int> capitanes; // Y una lista de los capitanes actuales

int capitan(int a) {
	// Encuentra el capitan del conjunto del que forma parte el nodo a
	if (a == par[a])
		return a;
	// Antes de retornarlo, aplanamos el arbol para ser eficientes
	return par[a] = capitan(par[a]);
}

void juntarGrupos(int i, int j) {
	// Junta los grupos del nodo i y el nodo j
	if (i == j)
		return;
	int capitan_i = capitan(i);
	int capitan_j = capitan(j);
	par[capitan_j] = capitan_i;
	auto it = find(capitanes.begin(), capitanes.end(), capitan_j);
	capitanes.erase(it, it+1);
}

void solve(int N, int C) {
	if (C == 1) {
		par.assign(N, 0);
		return;
	}
	par = vector<int>(N);
	for (int i = 0; i < N; i++)
		par[i] = i;
 
	capitanes = {};
	int ans, costumesDiscovered = 0;
	for (int i = 0; i < N; i++) {
		if (N - i == C - costumesDiscovered)
			continue;
 
        // comprobaremos si hay un conjunto al que añadir a la persona
		if(capitanes.size()) {
			cout << (int)capitanes.size()+1 << " ";
			for (int r: capitanes)
				cout << r+1 << ' ';
			cout << i+1 << '\n';
			cin >> ans;
			if (ans == (int) capitanes.size()) {
			    // hay un conjunto -> hacemos búsqueda binaria para encontrar cuál
				int lo = 0, hi = (int) capitanes.size()-1, mid, k = 0;
				while(lo <= hi) {
					if (lo == hi) {
						k = lo;
						break;
					}
					mid = lo + (hi-lo)/2;
					cout << (mid-lo+2) << " ";
					for (int j = lo; j <= mid; j++)
						cout << capitanes[j]+1 << ' ';
					cout << i+1 << '\n';
					cin >> ans;
					if (ans == (mid-lo+1)) {
						hi = mid;
						k = mid;
					} else lo = mid+1;
				}
				juntarGrupos(i, capitanes[k]);
			}
		}
 
		// esta persona forma un conjunto nuevo
		if (par[i] == i) {
			costumesDiscovered++;
			capitanes.push_back(i);
		}
	}
}
 
int main() {
	int N, C;
	cin >> N;
	cout << N;
	for (int i = 1; i <= N; i++)
		cout << " " << i;
	cout << '\n';
	cin >> C;
	solve(N, C);
	map<int, int> roots;
	int c = 1;
	for (int i = 0; i < N; i++) {
		if (roots.find(capitan(i)) == roots.end()) {
			roots[capitan(i)] = c++;
		}
	}
	int costumes[N];
	for (int i = 0; i < N; i++)
		costumes[i] = roots[capitan(i)];
	cout << "0";
	for (int i = 0; i < N; i++)
		cout << " " << costumes[i];
	cout << '\n';
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 3 ms 436 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 3 ms 440 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 436 KB Output is correct
4 Correct 3 ms 432 KB Output is correct
5 Correct 2 ms 432 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 2 ms 432 KB Output is correct