제출 #44404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44404		MatheusLealV	사육제 (CEOI14_carnival)	C++17	100 / 100	18 ms	588 KiB

carnival

#include <bits/stdc++.h>
#define N 200
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)
{
	/*set<int> ss;

	for(auto x: v) ss.insert(cor[x]);

	return ss.size();
	*/

	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++) cin>>cor[i];

	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;
		}
	}
  
  	cout<<"0 ";

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

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

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

	cout<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

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

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