Submission #749949

#	Time	Username	Problem	Language	Result	Execution time	Memory
749949		anhduc2701	Carnival (CEOI14_carnival)	C++17	0 / 100	6 ms	336 KiB

carnival

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int ask(vector<int> &a)
{
    cout << a.size() << " ";
    for (auto v : a)
    {
        cout << v << " ";
    }
    cout << endl;
    int d;
    cin >> d;
    return d;
}
int pa[maxn];
vector<int> get(vector<int> &a, int l, int r)
{
    vector<int> cac;
    for (int i = l; i <= r; i++)
    {
        cac.pb(a[i]);
    }
    return cac;
}
vector<int> dnc(int l, int r)
{
    if (l == r)
    {
        vector<int> d;
        d.pb(l);
        return d;
    }
    int mid = (l + r) / 2;
    vector<int> k1 = dnc(l, mid);
    vector<int> k2 = dnc(mid + 1, r);
    vector<int> id = k1;
    for (auto v : k2)
    {
        int l = 0;
        int r = k1.size() - 1;
        vector<int> d = k1;
        d.pb(v);
        if (ask(d) == k1.size()+1)
        {
            id.pb(v);
        }
        else
        {
            int ans = -1;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                vector<int> k = get(k1, l, mid);
                k.pb(v);
                if (ask(k) == mid-l+1)
                {
                    ans = mid;
                    r = mid - 1;
                }
                else
                {
                    l = mid + 1;
                }
            }
            pa[v] = k1[ans];
        }
    }
    return id;
}
int fin(int x)
{
    if (x == pa[x])
        return x;
    return pa[x] = fin(pa[x]);
}
signed main()
{
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        pa[i] = i;
    }
    vector<int> an = dnc(1, n);
    cout << "0 ";
    for (int i = 1; i <= n; i++)
    {
        int k = fin(i);
        int d = lower_bound(an.begin(), an.end(), k) - an.begin();
        cout << d << " ";
    }
}

Compilation message (stderr)

carnival.cpp: In function 'std::vector<int> dnc(int, int)':
carnival.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         if (ask(d) == k1.size()+1)
      |             ~~~~~~~^~~~~~~~~~~~~~

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