Submission #752647

#	Time	Username	Problem	Language	Result	Execution time	Memory
752647		benjaminkleyn	Carnival (CEOI14_carnival)	C++17	100 / 100	10 ms	316 KiB

carnival

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
bool done[150];
int val[150];

int query(const vector<int> &peoples, int l = 0, int r = 149, int extra = -1)
{
    cout << min((int)peoples.size(), r + 1) - l + (extra != -1);
    for (int i = l; i <= r && i < peoples.size(); i++)
        cout << ' ' << peoples[i] + 1;
    if (extra != -1)
        cout << ' ' << extra + 1;
    cout << '\n';

    cout.flush();
    int result;
    cin >> result;
    return result;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    vector<int> a = {0};
    done[0] = true;
    int cur = 1;
    for (int i = 1; i < n; i++)
    {
        a.push_back(i);
        if (query(a) > cur)
            cur++, done[i] = true;
        else
            a.pop_back();
    }

    int c = 0;
    for (int i : a)
        val[i] = c++;

    for (int i = 0; i < n; i++)
        if (!done[i])
        {
            // binary search in a to find the same costume.
            int lo = 0, hi = c - 1, mid;
            while (lo < hi)
            {
                mid = (lo + hi) / 2;
                if (query(a, lo, mid, i) == mid - lo + 1)
                    hi = mid;
                else
                    lo = mid + 1;
            }
            val[i] = val[a[lo]];
        }

    cout << '0';
    for (int i = 0; i < n; i++)
        cout << ' ' << val[i] + 1;
    cout << '\n';

    return 0;
}

Compilation message (stderr)

carnival.cpp: In function 'int query(const std::vector<int>&, int, int, int)':
carnival.cpp:12:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = l; i <= r && i < peoples.size(); i++)
      |                               ~~^~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20