Submission #131825

#	Time	Username	Problem	Language	Result	Execution time	Memory
131825		bogdan10bos	Carnival (CEOI14_carnival)	C++14	20 / 100	66 ms	852 KiB

carnival

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 155;

int N, rem;
int f[NMAX];

map< vector<int>, int > mp;
mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());


int ask(vector<int> v)
{
	sort(begin(v), end(v));
	if(mp.count(v))	return mp[v];

	printf("%d ", int(v.size()));
	for(auto x: v)	printf("%d ", x);
	printf("\n");
	fflush(stdout);

	int ans;
	scanf("%d", &ans);
	mp[v] = ans;
	return ans;
}

int F(int x)
{
	if(f[x] == x)	return x;
	return f[x] = F(f[x]);
}

void finish()
{
	vector<int> sol;
	sol.resize(N + 2);
	int K = 0;
	for(int i = 1; i <= N; i++)
		if(sol[i] == 0)
		{
			K++;
			for(int j = i; j <= N; j++)
				if(F(i) == F(j))
					sol[j] = K;
		}

	printf("0 ");
	for(int i = 1; i <= N; i++)
		printf("%d ", sol[i]);
	printf("\n");
	fflush(stdout);
	exit(0);
}

void unite(int x, int y)
{
	int fx = F(x), fy = F(y);
	if(fx == fy)	return;
	f[fy] = fx;
	rem--;
	if(rem == 0)	finish();
}

vector<int> reduce(vector<int> v)
{
	vector<int> a;
	for(int i = 0; i < (int)v.size(); i++)
	{
		int x = v[i];
		bool ok = true;
		for(auto y: a)
			if(F(x) == F(y))
			{
				ok = false;
				break;
			}
		if(ok)	a.push_back(x);
	}
	return a;
}

void solve(vector<int> v)
{
	shuffle(v.begin(), v.end(), g);
	if(v.size() <= 1)	return;
	int cnt = ask(v);
	if(cnt == (int)v.size())	return;
	if(cnt == 1)
		for(auto x: v)	unite(x, v[0]);

	if(rem == 0)	return;

	v = reduce(v);

	if((int)v.size() <= 2)
	{
		solve(v);
		return;
	}

	int msk = 0;
	for(int b = 0; (1 << b) < (int)v.size(); b++)
	{
		msk |= (1 << b);
		vector<int> vec[2];
		for(int i = 0; i < (int)v.size(); i++)
			vec[ (i >> b) & 1 ].push_back(v[i]);

		solve(vec[0]);
		solve(vec[1]);
	}

	vector<int> vec[2];
	int k = 0;
	for(int i = 0; i < v.size(); i++)
		for(int j = i + 1; j < v.size(); j++)
			if( (i & j) == 0 && ( (i ^ msk) & (j ^ msk) ) == 0 )
			{
				vec[k].push_back(v[i]);
				vec[k].push_back(v[j]);
				k ^= 1;
			}

	solve(vec[0]);
	solve(vec[1]);
}

int main()
{
	scanf("%d", &N);
	vector<int> v;
	for(int i = 1; i <= N; i++)	f[i] = i, v.push_back(i);

	rem = N - ask(v);
	solve(v);
	finish();
	return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'void solve(std::vector<int>)':
carnival.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++)
                 ~~^~~~~~~~~~
carnival.cpp:119:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < v.size(); j++)
                      ~~^~~~~~~~~~
carnival.cpp: In function 'int ask(std::vector<int>)':
carnival.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &ans);
  ~~~~~^~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~

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