# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
50218 | rondojim | medians (balkan11_medians) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int A[2 * MAXN], B[MAXN], N, cnt[2 * MAXN];
set<int> S;
int main(){
scanf("%d", &N);
for(int i=1; i<=N; ++i){ scanf("%d", &B[i]); cnt[B[i]]++; }
for(int i=1; i<2*N; ++i) S.insert(i);
for(int i=1; i<N; ++i){ if(S.find(B[i]) != S.end()) S.erase(S.find(B[i])); }
A[1] = B[1];
for(int i=N; i>=2; --i){
int p = B[i - 1], c = B[i];
set<int>::iterator it;
if(c > p){
for(int j=2*i-1; j>=2*i-2; --j){
auto it = S.lower_bound(B[i]);
if(it != S.end()) A[j] = *it;
if(it != S.end()) S.erase(it);
}
}
else if(c < p){
for(int j=2*i-1; j>=2*i-2; --j){
it = S.lower_bound(B[i - 1]);
if(it != S.end())
else if(*it >= B[i - 1]) --it;
if(it != S.end()) A[j] = *it;
if(it != S.end())S.erase(it);
}
}
else{
it = S.upper_bound(B[i]);
if(it != S.end()) A[2 * i - 1] = *it;
if(it != S.end()) S.erase(it);
it = S.lower_bound(B[i]);
if(it == S.end()) --it;
else if(*it >= B[i]) --it;
A[2 * i - 2] = *it;
if(it != S.end()) S.erase(it);
}
if(cnt[B[i - 1]] == 1) S.insert(B[i - 1]);
else cnt[B[i - 1]]--;
}
for(int i=1; i<2*N; ++i) printf("%d ", A[i]);
return 0;
}