Submission #44405

#	Time	Username	Problem	Language	Result	Execution time	Memory
44405		MatheusLealV	Carnival (CEOI14_carnival)	C++17	0 / 100	16 ms	636 KiB

carnival

#include <bits/stdc++.h>
#define N 200
#define MAX_SQRT 20
using namespace std;

int cor[N], n, raiz, used[N], pai[N], peso[N], comprimir[N], cnt;

vector< int > v [20];

int query(vector<int> v)
{
	if(v.size() == 0) return 0;

	cout<<v.size()<<" ";

	for(auto x: v) cout<<x<<" ";

	cout<<endl;

	int k;

	cin>>k;

	return k;
}

int Find(int x)
{
	if(x == pai[x]) return x;

	return pai[x] = Find(pai[x]);
}

void join(int a, int b)
{
	a = Find(a), b = Find(b);

	if(peso[a] > peso[b]) pai[b] = a;

	else if(peso[a] < peso[b]) pai[a] = b;

	else pai[a] = b, peso[b] ++;
}

int main()
{
	cin>>n;

	raiz = ceil(sqrt(n));

	for(int i = 1; i <= n; i ++)
	{
		pai[i] = i;

		int bloco = i/raiz;

		v[bloco].push_back(i);
	}

	for(int sqrt = 0; sqrt < 20; sqrt ++)
	{
		if(v[sqrt].empty()) continue;

		sort(v[sqrt].begin(), v[sqrt].end());

		int qtd = query(v[sqrt]);

		for(int i = v[sqrt].back() + 1; i <= n; i++)
		{
			if(binary_search(v[sqrt].begin(), v[sqrt].end(), i)) continue;

			v[sqrt].push_back(i);

			if(query(v[sqrt]) == qtd) sort(v[sqrt].begin(), v[sqrt].end());

			else v[sqrt].pop_back();
		}
	}

	for(int sqrt = 0; sqrt < 20; sqrt ++)
	{
		for(int i = 0; i < v[sqrt].size(); i++)
		{
			for(int j = i + 1; j < v[sqrt].size(); j++)
			{
				if(used[ v[sqrt][j] ] == 1) continue;

				vector<int> vv(2);

				vv[0] = v[sqrt][i], vv[1] = v[sqrt][j];

				if(query(vv) == 1)
				{
					used[ vv[1] ] = 1;

					join(vv[0], vv[1]);
				}
			}

			used[ v[sqrt][i] ] = 1;
		}
	}

	for(int i = 1; i <= n; i++)
	{
		int f = Find(i);

		if(!comprimir[ f ]) comprimir[f] = ++ cnt;

		cout<<comprimir[f]<<' ';
	}

	cout<<"\n";
}

Compilation message (stderr)

carnival.cpp: In function 'int main()':
carnival.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v[sqrt].size(); i++)
                  ~~^~~~~~~~~~~~~~~~
carnival.cpp:84:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = i + 1; j < v[sqrt].size(); j++)
                       ~~^~~~~~~~~~~~~~~~

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