G.cpp

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#else
    #define NDEBUG
    #pragma GCC optimize("O3")
    #pragma GCC target("arch=corei7-avx")
#endif
#include <bits/stdc++.h>
#define int long long
#define float long double
#define all(x) begin(x), end(x)
using namespace std;

template<class A>
void addlog(A a)
{
    cerr << a << endl;
}

template<class A, class... B>
void addlog(A a, B... b)
{
    cerr << a << ' '; addlog(b...);
}

template<class T>
ostream & operator <<(ostream & out, vector<T> v)
{
    for (T & e : v)
    {
        out << e << ' ';
    }
    return out << endl;
}





void ask(vector<int> t, int & left, int & right)
{
    assert(is_sorted(all(t)));
    cout << t.size() << ' ';
    for (int e : t)
    {
        cout << e << ' ';
    }
    cout << endl;
    int res;
    cin >> res;
    if (res < 0)
    {
        exit(0);
    }
    if (res == 0)
    {
        right = min(right, t.front() - 1);
    }
    else if (res
     == (int)t.size())
    {
        left = max(left, t.back() + 1);
    }
    else
    {
        left = max(left, t[res - 1] + 1);
        right = min(right, t[res] - 1);
    }
}


//~ void play(int k, int m, int l)
//~ {
    //~ // k = min
    //~ // m = max
    //~ // l = least steps
    //~ assert(l > 0);
    //~ addlog("playing", k, m, "least", l);
    //~ if (k == 1)
    //~ {
        //~ if (l == 5)
        //~ {
            //~ ask({ 10'000 }, k, m);
            //~ play(k, m, l - 1);
        //~ }
        //~ if (l == 4)
        //~ {
            //~ ask({ 79 }, k, m);
            //~ play(k, m, l - 1);
        //~ }
        //~ if (l == 3)
        //~ {
            //~ ask({ 6 }, k, m);
            //~ play(k, m, l - 1);
        //~ }
        //~ if (l == 2)
        //~ {
            //~ ask({ 2 }, k, m);
            //~ play(k, m, l - 1);
        //~ }
        //~ if (l == 1)
        //~ {
            //~ ask({ 1 }, k, m);
            //~ play(k, m, l - 1);
        //~ }
    //~ }
    //~ else
    //~ {
        //~ if (k == 3)
        //~ {
            //~ assert(m == 5);
            //~ ask({ 3, 4, 5 }, k, m);
            //~ play(k, m, l - 1);
        //~ }
        //~ else
        //~ {
            //~ assert(k > 3);
            //~ vector<int> t(k);
            //~ int d = (m - k + 1) / k;
            //~ for (int i = 0; i < k; ++i)
            //~ {
                //~ t[i] = k + (i + 1) * d;
            //~ }
            //~ t[0] -= 2;
            //~ t[1] -= 1;
            //~ t[k - 2] += 2;
            //~ t[k - 1] += 3;
            //~ ask(t, k, m);
            //~ play(k, m, l - 1);
        //~ }
    //~ }
    //~ assert(false);
//~ }

map<pair<int, int>, bool> mem[10];

bool good(int k, int m, int l)
{
    //~ addlog(k, m, l);
    if (l <= 0) return false;
    if (m - k + 1 <= k) return true;
    if (l == 1) return false;
    if (mem[l].count({k, m})) return mem[l][{k, m}];
    for (int i = 0, ee = min(k, 10000LL); i < ee; ++i)
    {
        int mid, lef = k, rig = m;
        assert(good(k, lef - 1, l - 1));
        for (; rig - lef > 1; )
        {
            mid = (lef + rig) / 2;
            if (good(k, mid - 1, l - 1))
            {
                lef = mid;
            }
            else
            {
                rig = mid;
            }
        }
        assert(good(k, lef - 1, l - 1));
        k = lef + 1;
    }
    //~ addlog("---");
    return mem[l][{k, m}] = good(k, m, l - 1);
}


bool play(int k, int m, int l)
{
    addlog("playing", k, m, l);
    assert(good(k, m, l));
    vector<int> t;
    t.reserve(min(k, 10000LL));
    if (l == 1)
    {
        for (int i = k; i <= m; ++i)
        {
            t.push_back(i);
        }
        assert((int)t.size() <= k);
        ask(t, k, m);
        assert(false);
    }
    for (int i = 0, ee = min(k, 10000LL), kk = k; i < ee; ++i)
    {
        int mid, lef = kk, rig = m;
        assert(good(kk, lef - 1, l - 1));
        for (; rig - lef > 1; )
        {
            mid = (lef + rig) / 2;
            if (good(kk, mid - 1, l - 1))
            {
                lef = mid;
            }
            else
            {
                rig = mid;
            }
        }
        assert(good(kk, lef - 1, l - 1));
        if (k <= lef && lef <= m) t.push_back(lef);
        kk = lef + 1;
    }
    ask(t, k, m);
    play(k, m, l - 1);
}






const int INF = 1e18 + 15;



int32_t main()
{
    play(1, 10004205361450474LL, 5);
    return 0;
}