oj.uz

Submission #867921

# Submission time Handle Problem Language Result Execution time Memory
867921 2023-10-29T19:29:14 Z borisAngelov Carnival (CEOI14_carnival) C++17
100 / 100
 12 ms 712 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 460 KB Output is correct
2 Correct 11 ms 460 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 3 ms 464 KB Output is correct
5 Correct 8 ms 460 KB Output is correct
6 Correct 8 ms 468 KB Output is correct
7 Correct 8 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 460 KB Output is correct
2 Correct 12 ms 712 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 9 ms 460 KB Output is correct
6 Correct 8 ms 468 KB Output is correct
7 Correct 9 ms 456 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 460 KB Output is correct
2 Correct 10 ms 460 KB Output is correct
3 Correct 9 ms 464 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 7 ms 464 KB Output is correct
6 Correct 7 ms 464 KB Output is correct
7 Correct 9 ms 468 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB Output is correct
2 Correct 12 ms 464 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 4 ms 460 KB Output is correct
5 Correct 8 ms 464 KB Output is correct
6 Correct 6 ms 464 KB Output is correct
7 Correct 9 ms 468 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 464 KB Output is correct
2 Correct 12 ms 460 KB Output is correct
3 Correct 7 ms 464 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 6 ms 464 KB Output is correct
6 Correct 4 ms 464 KB Output is correct
7 Correct 3 ms 468 KB Output is correct