Submission #860944

#TimeUsernameProblemLanguageResultExecution timeMemory
860944BlancaHMCarnival (CEOI14_carnival)C++14
100 / 100
4 ms596 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...