제출 #112499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
112499		KCSC	사육제 (CEOI14_carnival)	C++14	100 / 100	11 ms	432 KiB

carnival

#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20