oj.uz

Submission #44406

# Submission time Handle Problem Language Result Execution time Memory
44406 2018-04-02T03:43:28 Z MatheusLealV Carnival (CEOI14_carnival) C++17
100 / 100
 19 ms 588 KB 
#include <bits/stdc++.h>
#define N 200
#define MAX_SQRT 20
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)
{
	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 ++)
	{
		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;
 }

Compilation message

carnival.cpp: In function 'int main()':
carnival.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v[sqrt].size(); i++)
                  ~~^~~~~~~~~~~~~~~~
carnival.cpp:84: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 18 ms 248 KB Output is correct
2 Correct 13 ms 440 KB Output is correct
3 Correct 14 ms 440 KB Output is correct
4 Correct 15 ms 552 KB Output is correct
5 Correct 10 ms 552 KB Output is correct
6 Correct 9 ms 552 KB Output is correct
7 Correct 14 ms 552 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 552 KB Output is correct
2 Correct 10 ms 564 KB Output is correct
3 Correct 9 ms 564 KB Output is correct
4 Correct 12 ms 564 KB Output is correct
5 Correct 13 ms 568 KB Output is correct
6 Correct 15 ms 568 KB Output is correct
7 Correct 15 ms 568 KB Output is correct

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 572 KB Output is correct
2 Correct 16 ms 572 KB Output is correct
3 Correct 11 ms 572 KB Output is correct
4 Correct 14 ms 572 KB Output is correct
5 Correct 18 ms 572 KB Output is correct
6 Correct 18 ms 572 KB Output is correct
7 Correct 16 ms 572 KB Output is correct

Subtask #5
20.0 / 20.0

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