Submission #1145567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145567		slayer	medians (balkan11_medians)	C++20	100 / 100	33 ms	2864 KiB

medians

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

const int N = 1e5;
bool vis[2 * N];

int mx, mn;

void updateMin() {
    
    while ( vis[mn]) mn ++;
    
    return ;
    
}

void updateMax() {
    
    while ( vis[mx]) mx --;
    
    return ;
}

int main() {
    
    int n;
    cin >> n;
    
    vector<int> a(n);
    for ( int i = 0; i < n; i ++)
        cin >> a[i];
        
    vector<int> b(n * 2 - 1);
    
    b[0] = a[0];
    vis[a[0]] = 1;
    
    mn = 1;
    mx = n * 2 - 1;
    
    for ( int i = 1; i < n; i ++) {
        
        if ( a[i] == a[i - 1]) {
            
            updateMin();
            b[i * 2 - 1] = mn;
            vis[mn] = 1;
            
            updateMax();
            b[i * 2] = mx;
            vis[mx] = 1;
        }
        else if ( a[i] > a[i - 1]) {
            
            if ( vis[a[i]]) {
                
                updateMax();
                b[i * 2 - 1] = mx;
                vis[mx] = 1;
                
                updateMax();
                b[i * 2] = mx;
                vis[mx] = 1;
                
            }
            else {
                
                b[i * 2 - 1] = a[i];
                vis[a[i]] = 1;
                
                updateMax();
                b[i * 2] = mx;
                vis[mx] = 1;
            }
        }
        else {
            
            if ( vis[a[i]]) {
                
                updateMin();
                b[i * 2 - 1] = mn;
                vis[mn] = 1;
                
                updateMin();
                b[i * 2] = mn;
                vis[mn] = 1;
                
            }
            else {
                
                b[i * 2 - 1] = a[i];
                vis[a[i]] = 1;
                
                updateMin();
                b[i * 2] = mn;
                vis[mn] = 1;
            }
        }
    }
    
    for ( int i = 0; i < 2 * n - 1; i ++)
        cout << b[i] << " ";
    
    return 0;
}

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