Competitive Programming Solutions

1419D2 - Sages Birthday

07 Jan 2021 — Tags: binary_search,greedy — URL

Given a number of desired cheap ice, $x$, pick the $x$ smallest numbers and alternate them with the larges ones. Binary search to find $x$.

Editorial.

Time complexity: $O(n \log{n})$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int bs(int l, int r, function<bool(int)> p)
{
    while (l < r)
    {
        int m = l + (r - l + 1) / 2;
        if (p(m))
            l = m;
        else
            r = m - 1;
    }
    return l;
}
int solve(vi &a)
{
    int n = (int)(a).size();
    sort(begin(a), end(a));
    auto ok = [&a, n](int x) {
        for (int i = 0; i < x; i++)
        {
            int j = x - i - 1, l = n - i - 2, r = n - i - 1;
            if (!(a[l] > a[j] and a[j] < a[r]))
                return false;
        }
        return true;
    };
    int x = bs(0, (n - 1) / 2, ok);
    if (x == 0)
        return x;
    int i = n - 1;
    vi left(a.begin(), a.begin() + x), right(a.begin() + x, a.end());
    while (left.size())
    {
        a[i--] = right.back();
        right.pop_back();
        a[i--] = left.back();
        left.pop_back();
    }
    while (right.size())
    {
        a[i--] = right.back();
        right.pop_back();
    }
    return x;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    for (auto &ai : a)
        cin >> ai;
    cout << solve(a) << endl;
    for (auto ai : a)
        cout << ai << " ";
    cout << endl;
    return 0;
}

Related posts