oj.uz

Submission #112499

# Submission time Handle Problem Language Result Execution time Memory
112499 2019-05-20T09:44:14 Z KCSC Carnival (CEOI14_carnival) C++14
100 / 100
 11 ms 432 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef HOME
int test[] = {0, 1, 2, 3, 4, 5, 5, 4, 3, 2, 1};
#endif 

int ask2(vector<int> list) {
#ifdef HOME
	set<int> values;
	for (int person : list) {
		values.insert(test[person]); }
	return values.size(); 
#else
	cout << list.size() << " ";
	for (int person : list) {
		cout << person << " "; }
	cout << endl;
	int answer; cin >> answer;
	return answer; 
#endif
	return -1; }

int ask(vector<int> list, int value) {
	list.push_back(value);
	for (int &person : list) {
		++person; }
	return ask2(list); }

vector<vector<int>> divide(int left, int right) {
	vector<vector<int>> groups;
	if (left == right) {
		groups.push_back(vector<int>(1, left));
		return groups; }
	else {
		int middle = (left + right) >> 1;
		vector<vector<int>> leftGroups = divide(left, middle),
												rightGroups = divide(middle + 1, right),
												combinedGroups;
		combinedGroups = leftGroups;
		for (int group = 0; group < rightGroups.size(); ++group) {
			vector<int> aux;
			for (int pos = 0; pos < leftGroups.size(); ++pos) {
				aux.push_back(leftGroups[pos].back()); }
			if (ask(aux, rightGroups[group].back()) == aux.size() + 1) {
				combinedGroups.push_back(rightGroups[group]); }
			else {
				int left = 0, right = (int) aux.size() - 1;
				while (left <= right) {
					int middle = (left + right) >> 1;
					vector<int> aux2;
					for (int pos = left; pos <= middle; ++pos) {
						aux2.push_back(aux[pos]); }
					if (ask(aux2, rightGroups[group].back()) == aux2.size() + 1) {
						left = middle + 1; }
					else {
						right = middle - 1; } }
				for (int person : rightGroups[group]) {
					combinedGroups[left].push_back(person); } } } 
		return combinedGroups; } } 

int main(void) {
	int N; cin >> N;
	vector<vector<int>> groups = divide(0, N - 1);
	vector<int> answer(N);
	for (int group = 0; group < groups.size(); ++group) {
		for (int person : groups[group]) {
			answer[person] = group + 1; } }
	cout << 0 << " ";
	for (int person : answer) {
		cout << person << " "; }
	cout << endl;
	return 0; }

Compilation message

carnival.cpp: In function 'std::vector<std::vector<int> > divide(int, int)':
carnival.cpp:41:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int group = 0; group < rightGroups.size(); ++group) {
                       ~~~~~~^~~~~~~~~~~~~~~~~~~~
carnival.cpp:43:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int pos = 0; pos < leftGroups.size(); ++pos) {
                      ~~~~^~~~~~~~~~~~~~~~~~~
carnival.cpp:45:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ask(aux, rightGroups[group].back()) == aux.size() + 1) {
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
carnival.cpp:54:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (ask(aux2, rightGroups[group].back()) == aux2.size() + 1) {
          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
carnival.cpp: In function 'int main()':
carnival.cpp:66:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int group = 0; group < groups.size(); ++group) {
                      ~~~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 256 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 4 ms 408 KB Output is correct
5 Correct 8 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 10 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 324 KB Output is correct
2 Correct 10 ms 256 KB Output is correct
3 Correct 4 ms 400 KB Output is correct
4 Correct 10 ms 384 KB Output is correct
5 Correct 4 ms 324 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 7 ms 256 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 304 KB Output is correct
2 Correct 8 ms 320 KB Output is correct
3 Correct 11 ms 256 KB Output is correct
4 Correct 9 ms 256 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 6 ms 324 KB Output is correct
7 Correct 9 ms 256 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 256 KB Output is correct
2 Correct 4 ms 324 KB Output is correct
3 Correct 8 ms 384 KB Output is correct
4 Correct 9 ms 384 KB Output is correct
5 Correct 9 ms 424 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 8 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 10 ms 384 KB Output is correct
3 Correct 9 ms 328 KB Output is correct
4 Correct 7 ms 432 KB Output is correct
5 Correct 7 ms 256 KB Output is correct
6 Correct 10 ms 420 KB Output is correct
7 Correct 5 ms 324 KB Output is correct