Submission #1065940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065940		coolboy19521	Carnival (CEOI14_carnival)	C++17	100 / 100	10 ms	700 KiB

carnival

#pragma GCC optimize("Ofast")
#pragma once
#include <bits/stdc++.h>

namespace ddr {
    #define bpc(bt) __builtin_popcountll(bt)
    #define bcl(bt) __builtin_clz(bt)
    #define alr(v) rbegin(v),rend(v)
    #define all(v) begin(v),end(v)
    #define si(v) ((ll)v.size())
    #define lob lower_bound
    #define upb upper_bound
    #define pub push_back
    #define pob pop_back
    #define mp make_pair
    #define ins insert
    #define se second
    #define fi first

    template<class T,size_t N> using ar = std::array<T, N>;
    template<class T,class U> using pi = std::pair<T, U>;
    template<class T> using pq = std::priority_queue<T>;
    template<class T> using mt = std::multiset<T>;
    template<class T> using ve = std::vector<T>;
    template<class T> using qu = std::queue<T>;
    typedef std::string str;
    typedef long double ld;
    typedef long long ll;

    using namespace std;

    const int iinf = INT_MAX;
    const ll inf = 1e18 + 18;
    const ll md = 1e9 + 7;
    const ll mo = 998244353;
}

using namespace ddr;

template<class T>
struct STree {
    vector<T> st;
    function<T(T,T)> f;
    T df, n;
    STree(T _n, T _df, function<T(T,T)> _f) {
        n = _n;
        df = _df;
        f = _f;
        st.assign(2 * (n + 1), _df);
    }
    void set(T v, T k) {
        st[v += n] = k;
        for (v /= 2; v; v /= 2)
            st[v] = f(st[v * 2], st[v * 2 + 1]);
    }
    T qry(T lo, T hi) {
        T r = df;
        for (lo += n, hi += n + 1; lo < hi; lo /= 2, hi /= 2) {
            if (lo & 1) r = f(r, st[lo ++]);
            if (hi & 1) r = f(r, st[-- hi]);
        }
        return r;
    }
};

template<class T>
struct FTree {
    vector<T> st;
    T n;
    FTree(T _n) {
        n = _n;
        st.assign(n + 1, 0);
    }
    void add(T v, T k) {
        for (; v <= n; v += v & -v)
            st[v] += k;
    }
    void set(T v, T k) {
        int bf = qrt(v, v);
        for (; v <= n; v += v & -v)
            st[v] += k - bf;
    }
    T qry(T lo, T hi) {
        lo --;
        T lq = 0;
        for (; 0 < lo; lo -= lo & -lo)
            lq += st[lo];
        T rq = 0;
        for (; 0 < hi; hi -= hi & -hi)
            rq += st[hi];
        return rq - lq;
    }
};

template<class T>
struct DSU {
    vector<T> par;
    DSU(T n) {
        par.assign(n + 1, -1);
    }
    T Find(T v) {
        if (0 > par[v]) return v;
        return par[v] = Find(par[v]);
    }
    bool Unite(T u, T v) {
        u = Find(u);
        v = Find(v);
        if (par[u] > par[v])
            swap(u, v);
        if (u == v)
            return false;
        par[u] += par[v];
        par[v] = u;
        return true;
    }
};

template<class T>
void show(vector<T> v, char bt) {
    for (T i : v) cout << i << bt;
    cout << '\n';
}

template<class T>
void show(T a[], size_t n, char bt) {
    for (size_t i = 0; i < n; i ++) cout << a[i] << bt;
    cout << '\n';
}

template<class T>
void show(T* a, size_t n, size_t m, char bt) {
    for (size_t i = 0; i < n; i ++)
        show(a[i], m, bt);
}

int main() {
    int n;
    cin >> n;

    ve<ve<int>> gr;

    auto check = [&](int x, int y) {
        ve<int> qry{y + 1};
        for (int i = 0; i <= x; i ++)
            for (int j : gr[i])
                qry.pub(j + 1);
        cout << si(qry) << ' ';
        show(qry, ' ');
        int rcv;
        cin >> rcv;
        return rcv == x + 1;
    };

    for (int i = n - 1; 0 <= i; i --) {
        int lo = 0, hi = si(gr);
        while (lo != hi) {
            int mi = (lo + hi) / 2;
            if (check(mi, i))
                hi = mi;
            else lo = mi + 1;
        }
        if (si(gr) != hi)
            gr[lo].pub(i);
        else gr.pub({i});
    }

    ve<int> an(n + 1);
    for (int i = 0; i < si(gr); i ++) {
        for (auto& j : gr[i])
            an[j + 1] = i + 1;
    }

    show(an, ' ');
}

Compilation message (stderr)

carnival.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~

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