oj.uz

Submission #867918

# Submission time Handle Problem Language Result Execution time Memory
867918 2023-10-29T19:24:24 Z borisAngelov Carnival (CEOI14_carnival) C++17
0 / 100
 13 ms 708 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;
}

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;
                }
            }

            if (l == i)
            {
                return 1;
            }

            dsu.connect(l, i);
        }
    }

    cout << 0 << " ";

    for (int i = 1; i <= n; ++i)
    {
        cout << 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 460 KB Integer 19 violates the range [1, 11]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 708 KB Integer 6 violates the range [1, 5]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 448 KB Output is correct
2 Incorrect 11 ms 456 KB Integer 11 violates the range [1, 8]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 460 KB Integer 5 violates the range [1, 4]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 504 KB Output is correct
2 Incorrect 9 ms 460 KB Integer 20 violates the range [1, 17]
3 Halted 0 ms 0 KB -