Submission #83761

#	Time	Username	Problem	Language	Result	Execution time	Memory
83761		popovicirobert	medians (balkan11_medians)	C++14	100 / 100	33 ms	4344 KiB

medians

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 1e5;

int arr[MAXN + 1], sol[2 * MAXN + 1];
bool vis[2 * MAXN + 1];

inline int get_max(int &b) {
    while(vis[b]) {
        b--;
    }
    vis[b] = 1;
    return b;
}

inline int get_min(int &a) {
    while(vis[a]) {
        a++;
    }
    vis[a] = 1;
    return a;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    sol[1] = arr[1];
    vis[arr[1]] = 1;
    int a = 1, b = 2 * n - 1;
    int p = 2;
    for(i = 2; i <= n; i++) {
        if(arr[i] == arr[i - 1]) {
            sol[p] = get_max(b);
            sol[p + 1] = get_min(a);
        }
        if(arr[i] > arr[i - 1]) {
            if(vis[arr[i]] == 0) {
                sol[p] = arr[i];
                vis[arr[i]] = 1;
                sol[p + 1] = get_max(b);
            }
            else {
                sol[p] = get_max(b);
                sol[p + 1] = get_max(b);
            }
        }
        if(arr[i] < arr[i - 1]) {
            if(vis[arr[i]] == 0) {
                sol[p] = arr[i];
                vis[arr[i]] = 1;
                sol[p + 1] = get_min(a);
            }
            else {
                sol[p] = get_min(a);
                sol[p + 1] = get_min(a);
            }
        }
        p += 2;
    }
    for(i = 1; i < 2 * n; i++) {
        cout << sol[i] << " ";
    }
    //cin.close();
    //cout.close();
    return 0;
}

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