oj.uz

답안 #112498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
112498 2019-05-20T09:39:31 Z KCSC 사육제 (CEOI14_carnival) C++14
0 / 100
 8 ms 428 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef HOME
int test[] = {0, 2, 1, 2, 3, 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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 428 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 256 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 324 KB Output is correct
2 Incorrect 8 ms 256 KB Integer 9 violates the range [1, 8]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 256 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 256 KB Output is correct
2 Incorrect 5 ms 324 KB Incorrect
3 Halted 0 ms 0 KB -