제출 #1326933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326933		paronmanukyan	중앙값 배열 (balkan11_medians)	C++20	100 / 100	17 ms	2872 KiB

medians

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

int main()
{
    FASTIO

    int n; 
    cin >> n;

    V<int> a(n + 1);
    rep(i, 1, n, 1) cin >> a[i];

    V<bool> used(2 * n + 1, false);
    V<int> ans(2 * n + 1);

    int l = 1, r = 2 * n - 1;

    function<int(int,int)> adjust = [&](int pos, int dir) -> int {
        for (int i = pos; i >= 1 && i <= 2 * n - 1; i += dir)
            if (!used[i]) return i;
        return -1;
    };

    function<void(int)> ml = [&](int pos) -> void {
        ans[pos] = l;
        used[l] = true;
        l = adjust(l, 1);
    };

    function<void(int)> mr = [&](int pos) -> void {
        ans[pos] = r;
        used[r] = true;
        r = adjust(r, -1);
    };

    ans[1] = a[1];
    used[a[1]] = true;
    if (a[1] == l) l = adjust(l, 1);
    if (a[1] == r) r = adjust(r, -1);

    rep(i, 2, n, 1) {

        if (a[i] == a[i - 1]) {
            ml(2 * i - 2);
            mr(2 * i - 1);
            continue;
        }

        if (a[i] > a[i - 1]) {
            if (used[a[i]]) mr(2 * i - 2);
            else {
                ans[2 * i - 2] = a[i];
                used[a[i]] = true;
                if (a[i] == l) l = adjust(l, 1);
                if (a[i] == r) r = adjust(r, -1);
            }
            mr(2 * i - 1);
        }
        else {
            if (used[a[i]]) ml(2 * i - 2);
            else {
                ans[2 * i - 2] = a[i];
                used[a[i]] = true;
                if (a[i] == l) l = adjust(l, 1);
                if (a[i] == r) r = adjust(r, -1);
            }
            ml(2 * i - 1);
        }
    }

    rep(i, 1, 2 * n - 1, 1)
        cout << ans[i] << " ";
}

• Subtask 1: 65 / 65
• Subtask 2: 35 / 35