Submission #49959

#	Time	Username	Problem	Language	Result	Execution time	Memory
49959		mra2322001	medians (balkan11_medians)	C++14	95 / 100	119 ms	13244 KiB

medians

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100002;
const int R = 2*N;

int n, a[N], b[R], dd[R], save[N];
int d[2*N];
set <int> s;

void up(){
    for(int i = 1; i < n; i++){
        d[a[i]] = 1;
    }
    for(int i = 1; i <= 2*n - 1; i++){
        if(d[i]==0) s.insert(i);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
  
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i]; b[1] = a[1];
    for(int i = 2; i <= n; i++){
        if(dd[a[i]]==0) dd[a[i]] = i;
        if(a[i] > a[i - 1]){
            /// 1 nho hon, 3 lon hon, 2 nguoc lai
            save[i] = 3;
        }
        else if(a[i] < a[i - 1]) save[i] = 1;
        else save[i] = 2;
    }
    up();
    for(int i = n; i > 1; i--){
        /// 2*i - 1, 2*i - 2
        if(save[i]==1){
            if(dd[a[i]]==i){
                b[2*i-1] = a[i];
                auto it = s.lower_bound(a[i]); --it;
                b[2*i-2] = *it;
                s.erase(a[i]); s.erase(*it);
            }
            else{
                auto it = s.lower_bound(a[i]); --it;
                b[2*i-1] = *it; s.erase(*it);
                it = s.lower_bound(a[i]); --it;
                b[2*i-2] = *it; s.erase(*it);
            }
        }
        else if(save[i]==2){
            auto it = s.lower_bound(a[i]); --it;
            b[2*i-1] = *it; s.erase(*it);
            it = s.upper_bound(a[i]);
            b[2*i-2] = *it; s.erase(*it);
        }
        else{
            if(dd[a[i]]==i){
                b[2*i-1] = a[i]; s.erase(a[i]);
                auto it = s.lower_bound(a[i]);
                b[2*i-2] = *it; s.erase(*it);
            }
            else{
                auto it = s.upper_bound(a[i]);
                b[2*i-1] = *it; s.erase(*it);
                it = s.upper_bound(a[i]);
                b[2*i-2] = *it; s.erase(it);
            }
        }
    }
    for(int i = 1; i < 2*n; i++) cout << b[i] << " ";
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:24:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i = 1; i <= n; i++) cin >> a[i]; b[1] = a[1];
     ^~~
medians.cpp:24:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i = 1; i <= n; i++) cin >> a[i]; b[1] = a[1];
                                              ^

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