Submission #867921

#	Time	Username	Problem	Language	Result	Execution time	Memory
867921		borisAngelov	Carnival (CEOI14_carnival)	C++17	100 / 100	12 ms	712 KiB

carnival

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1005;

int n;

struct DSU
{
    int par[maxn];
    int sz[maxn];

    void build(int n)
    {
        for (int i = 1; i <= n; ++i)
        {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int node)
    {
        if (node == par[node])
        {
            return node;
        }

        return par[node] = root(par[node]);
    }

    void connect(int x, int y)
    {
        x = root(x);
        y = root(y);

        if (x == y)
        {
            return;
        }

        if (sz[x] < sz[y])
        {
            par[x] = y;
            sz[y] += sz[x];
        }
        else
        {
            par[y] = x;
            sz[x] += sz[y];
        }
    }
};

DSU dsu;

int query(const vector<int>& indexes)
{
    cout << indexes.size() << " ";

    for (int i = 0; i < indexes.size(); ++i)
    {
        cout << indexes[i] << ' ';
    }

    cout << endl;

    int answer;

    cin >> answer;

    return answer;
}

int compressed[maxn];
int currColor = 0;

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    dsu.build(n);

    for (int i = 1; i <= n; ++i)
    {
        vector<int> indexes;

        for (int j = 1; j <= i - 1; ++j)
        {
            indexes.push_back(j);
        }

        int diffWithout = (indexes.empty() ? 0 : query(indexes));

        indexes.push_back(i);

        int diffWith = query(indexes);

        if (diffWith == diffWithout) // => i is not a root
        {
            int l = 1;
            int r = i - 1;

            while (l <= r)
            {
                int mid = (l + r) / 2;

                vector<int> preffix;

                for (int j = 1; j <= mid; ++j)
                {
                    preffix.push_back(j);
                }

                diffWithout = query(preffix);

                preffix.push_back(i);

                diffWith = query(preffix);

                if (diffWith == diffWithout)
                {
                    r = mid - 1;
                }
                else
                {
                    l = mid + 1;
                }
            }

            dsu.connect(l, i);
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        if (i == dsu.root(i))
        {
            compressed[i] = ++currColor;
        }
    }

    cout << 0 << " ";

    for (int i = 1; i <= n; ++i)
    {
        cout << compressed[dsu.root(i)] << ' ';
    }

    cout << endl;

    return 0;
}

Compilation message (stderr)

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

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