Submission #26618694

---

Source Code Expand

// {{{
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define debug(x...)
#define debug_arr(x...)
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
// }}}

// 10 / 5 - 7 /2 - 9 / 8
// (10 * 7 / (5 * 2)  -   9 / 8
//
// 10 8 9 7
// 10 * 8 / (9 / 7)
//
// a / b ---   c  / d

// a * c / (b / d)
// a / d ---- c / b  ----- c / b > 1 b < c

//  1 2 3 4 5 6 4 2 3 1
//  6 /2  * 3 /  1
//  6 /1

const int N = 2e5 + 10;
int n;
int a[N];
bool v[N];
int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> n)
    {
        clr(v, 0);
        for (int i = 1; i <= n; ++i) cin >> a[i];

        int st = 1;
        while (1)
        {
            if (st > n) break;

            int bg = st;
            while (bg + 1 <= n && a[bg + 1] >= a[bg]) bg++;
            if (bg == n) break;

            int ed = bg + 1;
            assert(a[ed] < a[bg]);
            while (ed + 1 <= n && a[ed + 1] <= a[ed]) ed++;

            v[bg] = v[ed] = 1;

            st = ed + 1;
            if (st > n) break;
        }
        for (int i = 1; i <= n; i++)
        {
            cout << v[i] << " ";
        }
        cout << '\n';
    }

    return 0;
}

Submission Info

Judge Result