oj.uz

Submission #44404

# Submission time Handle Problem Language Result Execution time Memory
44404 2018-04-02T03:39:41 Z MatheusLealV Carnival (CEOI14_carnival) C++17
100 / 100
 18 ms 588 KB 
#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";
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 15 ms 248 KB Output is correct
2 Correct 16 ms 308 KB Output is correct
3 Correct 12 ms 384 KB Output is correct
4 Correct 8 ms 440 KB Output is correct
5 Correct 13 ms 496 KB Output is correct
6 Correct 12 ms 496 KB Output is correct
7 Correct 13 ms 552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 572 KB Output is correct
2 Correct 15 ms 572 KB Output is correct
3 Correct 11 ms 572 KB Output is correct
4 Correct 12 ms 572 KB Output is correct
5 Correct 12 ms 572 KB Output is correct
6 Correct 15 ms 588 KB Output is correct
7 Correct 15 ms 588 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 588 KB Output is correct
2 Correct 16 ms 588 KB Output is correct
3 Correct 14 ms 588 KB Output is correct
4 Correct 10 ms 588 KB Output is correct
5 Correct 14 ms 588 KB Output is correct
6 Correct 13 ms 588 KB Output is correct
7 Correct 14 ms 588 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 588 KB Output is correct
2 Correct 18 ms 588 KB Output is correct
3 Correct 14 ms 588 KB Output is correct
4 Correct 14 ms 588 KB Output is correct
5 Correct 13 ms 588 KB Output is correct
6 Correct 15 ms 588 KB Output is correct
7 Correct 15 ms 588 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 588 KB Output is correct
2 Correct 15 ms 588 KB Output is correct
3 Correct 17 ms 588 KB Output is correct
4 Correct 14 ms 588 KB Output is correct
5 Correct 14 ms 588 KB Output is correct
6 Correct 13 ms 588 KB Output is correct
7 Correct 14 ms 588 KB Output is correct