oj.uz

답안 #131826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131826 2019-07-17T17:42:26 Z bogdan10bos 사육제 (CEOI14_carnival) C++14
100 / 100
 40 ms 680 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);
	v = reduce(v);
	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];
	int k = 0;
	for(int i = 0; i < (int)v.size(); i++)
		for(int j = i + 1; j < (int)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]);

	for(int b = 0; (1 << b) < (int)v.size(); b++)
	{
		//v = reduce(v);
		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]);
	}
}

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 '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:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 456 KB Output is correct
2 Correct 34 ms 504 KB Output is correct
3 Correct 23 ms 424 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 8 ms 248 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 17 ms 504 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 324 KB Output is correct
2 Correct 35 ms 552 KB Output is correct
3 Correct 17 ms 504 KB Output is correct
4 Correct 7 ms 408 KB Output is correct
5 Correct 8 ms 320 KB Output is correct
6 Correct 5 ms 408 KB Output is correct
7 Correct 12 ms 452 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 20 ms 356 KB Output is correct
3 Correct 40 ms 504 KB Output is correct
4 Correct 6 ms 320 KB Output is correct
5 Correct 12 ms 376 KB Output is correct
6 Correct 10 ms 376 KB Output is correct
7 Correct 35 ms 504 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 448 KB Output is correct
2 Correct 10 ms 448 KB Output is correct
3 Correct 13 ms 580 KB Output is correct
4 Correct 5 ms 248 KB Output is correct
5 Correct 13 ms 504 KB Output is correct
6 Correct 13 ms 376 KB Output is correct
7 Correct 33 ms 680 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 376 KB Output is correct
2 Correct 27 ms 552 KB Output is correct
3 Correct 30 ms 544 KB Output is correct
4 Correct 25 ms 492 KB Output is correct
5 Correct 9 ms 328 KB Output is correct
6 Correct 7 ms 408 KB Output is correct
7 Correct 8 ms 376 KB Output is correct