oj.uz

Submission #1065940

# Submission time Handle Problem Language Result Execution time Memory
1065940 2024-08-19T13:21:05 Z coolboy19521 Carnival (CEOI14_carnival) C++17
100 / 100
 10 ms 700 KB 
#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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 8 ms 600 KB Output is correct
4 Correct 6 ms 452 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 2 ms 432 KB Output is correct
7 Correct 5 ms 448 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 5 ms 448 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 6 ms 600 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 4 ms 692 KB Output is correct
7 Correct 4 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 10 ms 700 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 7 ms 600 KB Output is correct
7 Correct 5 ms 340 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 344 KB Output is correct
3 Correct 6 ms 600 KB Output is correct
4 Correct 7 ms 344 KB Output is correct
5 Correct 9 ms 444 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 6 ms 600 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 6 ms 344 KB Output is correct
4 Correct 6 ms 456 KB Output is correct
5 Correct 6 ms 344 KB Output is correct
6 Correct 6 ms 448 KB Output is correct
7 Correct 10 ms 600 KB Output is correct