sayounara.cpp

#include <cstdint>
#include <vector>
#include <cassert>
#include <iostream>

uint64_t query(int l, int r);
uint32_t get(int x);

namespace {

const int $n = 1000005;

int n;

uint64_t f(int x) {
    static bool has[$n];
    static uint64_t c[$n];
    if (has[x]) return c[x]; has[x] = 1;
    return c[x] = query(1, x) + query(x + 1, n);
}

template<class T, class F>
inline T first_that(T l, T r, F &&pred) {
    assert(l <= r); T ret = r + 1;
    while (l <= r) {
        const T mid = (l + r) >> 1;
        if (pred(mid)) r = (ret = mid) - 1;
        else l = mid + 1;
    }
    return ret;
}
}

std::vector<uint32_t> recover(int n) {
    ::n = n;
    int l = 1, r = n - 1;
    while (f(l) != f(r)) {
        int m = (l + r) >> 1;
        auto s = f(m);
        if (s == f(r)) {
            int t = first_that(l, m - 1, [s](int d) { return f(d) == s; });
            if (t == 1 || f(t - 1) > s) r = t - 1; else l = t;
        } else {
            int t = first_that(m + 1, r, [s](int d) { return f(d) != s; });
            if (t == n || f(t) < s) r = t - 1; else l = t;
        }
    }
    auto A = get(l), B = get(r + 1);
    int mp = (A < B)? l: (r + 1);
    std::vector<uint32_t> ans(n);
    ans[mp - 1] = std::min(A, B);
    uint64_t last = 0;
    for (int i = mp - 1; i; --i) {
        uint64_t cur = query(i, mp);
        ans[i - 1] = cur - last;
        last = cur;
    }
    last = 0;
    for (int i = mp + 1; i <= n; ++i) {
        uint64_t cur = query(mp, i);
        ans[i - 1] = cur - last;
        last = cur;
    }
    return ans;
}