Submission #154352

#	Time	Username	Problem	Language	Result	Execution time	Memory
154352		dolphingarlic	medians (balkan11_medians)	C++14	10 / 100	35 ms	3960 KiB

medians

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

bool visited[200000];
int seq[200000];
queue<int> l, g;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, curr;
    cin >> n >> seq[1];
    visited[seq[1]] = true;
    curr = seq[1];
    FOR(i, 1, n) {
        int x;
        cin >> x;
        if (curr == x) {
            l.push(2 * i);
            g.push(2 * i + 1);
        } else if (curr < x) {
            g.push(2 * i);
            g.push(2 * i + 1);
            if (!visited[x]) {
                seq[g.front()] = x;
                visited[x] = true;
                g.pop();
            }
        } else {
            l.push(2 * i);
            l.push(2 * i + 1);
            if (!visited[x]) {
                seq[l.front()] = x;
                visited[x] = true;
                l.pop();
            }
        }
        curr = x;
    }

    int indx = 1;
    while (l.size()) {
        while (visited[indx]) indx++;
        seq[l.front()] = indx++;
        l.pop();
    }
    while (g.size()) {
        while (visited[indx]) indx++;
        seq[g.front()] = indx++;
        g.pop();
    }

    FOR(i, 1, 2 * n) cout << seq[i] << ' ';
    cout << '\n';
    return 0;
}

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