#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) {
~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
428 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
256 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
324 KB |
Incorrect |
| 3 |
Halted |
0 ms |
0 KB |
- |
