Submission #770737

#	Time	Username	Problem	Language	Result	Execution time	Memory
770737		emad234	medians (balkan11_medians)	C++17	100 / 100	19 ms	2936 KiB

medians

#include <bits/stdc++.h>
#define all(v) ((v).bvin(),(v).end())
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 2e6 + 3;
bool vis[mxN];
int b[mxN];
int a[mxN];
int mx,mn;
void pshmx(){
  while(vis[mx]){
    mx--;
  }
}void pshmn(){
  while(vis[mn]){
    mn++;
  }
}
signed main()
{
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n;
  cin >>n;
  mx = 2 * n - 1;mn = 1;
  for(int i = 1;i <= n;i++) cin >> b[i];
  a[1] = b[1];
  vis[b[1]] = 1;
  pshmn();
  pshmx();
  for(int i = 2;i <= n;i++){
    int l = 2 * i - 2,r = 2 * i - 1;
    if(b[i - 1] < b[i]){
      if(!vis[b[i]]){
        a[l] = b[i];vis[a[l]] = 1;
      }
      else{
        pshmx();
        a[l] = mx;vis[mx] = 1;
        pshmx();
      }
      pshmx();
      a[r] = mx;vis[mx] = 1;
      pshmx();
    }
    if(b[i - 1] > b[i]){
      if(!vis[b[i]]){
        a[l] = b[i];vis[a[l]] = 1;
      }
      else{
        pshmn();
        a[l] = mn;vis[mn] = 1;
        pshmn();
      }
      pshmn();
      a[r] = mn;vis[mn] = 1;
      pshmn();
    }
    if(b[i - 1] == b[i]){
      pshmx();
      pshmn();
      a[l] = mn;vis[mn] = 1;
      a[r] = mx;vis[mx] = 1;
      pshmn();
      pshmx();
    }
  }
  for(int i = 1;i <= 2 * n - 1;i++){
    cout<<a[i]<<' ';
  }
}

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