oj.uz

Submission #131825

# Submission time Handle Problem Language Result Execution time Memory
131825 2019-07-17T17:38:18 Z bogdan10bos Carnival (CEOI14_carnival) C++14
20 / 100
 66 ms 852 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 580 KB Output is correct
2 Partially correct 58 ms 808 KB Partially correct
3 Correct 40 ms 680 KB Output is correct
4 Correct 17 ms 376 KB Output is correct
5 Correct 8 ms 324 KB Output is correct
6 Correct 3 ms 248 KB Output is correct
7 Partially correct 48 ms 764 KB Partially correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 456 KB Output is correct
2 Partially correct 64 ms 760 KB Partially correct
3 Correct 39 ms 556 KB Output is correct
4 Correct 13 ms 540 KB Output is correct
5 Correct 15 ms 552 KB Output is correct
6 Correct 11 ms 376 KB Output is correct
7 Correct 34 ms 552 KB Output is correct

Subtask #3
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 22 ms 540 KB Output is correct
3 Partially correct 55 ms 852 KB Partially correct
4 Correct 13 ms 376 KB Output is correct
5 Correct 22 ms 380 KB Output is correct
6 Correct 19 ms 424 KB Output is correct
7 Partially correct 66 ms 808 KB Partially correct

Subtask #4
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 424 KB Output is correct
2 Correct 33 ms 504 KB Output is correct
3 Correct 23 ms 588 KB Output is correct
4 Correct 5 ms 328 KB Output is correct
5 Correct 17 ms 448 KB Output is correct
6 Correct 16 ms 448 KB Output is correct
7 Partially correct 56 ms 760 KB Partially correct

Subtask #5
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 328 KB Output is correct
2 Partially correct 50 ms 760 KB Partially correct
3 Partially correct 59 ms 792 KB Partially correct
4 Partially correct 34 ms 836 KB Partially correct
5 Correct 33 ms 628 KB Output is correct
6 Correct 31 ms 504 KB Output is correct
7 Correct 16 ms 504 KB Output is correct