Submission #90590

#	Time	Username	Problem	Language	Result	Execution time	Memory
90590		314rate	medians (balkan11_medians)	C++14	5 / 100	27 ms	4892 KiB

medians

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N=2*100000+5;

int n;
int b[N];
int v[N];

bool viz[N];

void upd(int i,int x)
{
    v[i]=x;
    viz[x]=1;
}

int mip=1;
int mxp;

int f_mi()
{
    while(viz[mip])
    {
        mip++;
    }
    return mip;
}

int f_mx()
{
    while(viz[mxp])
    {
        mxp--;
    }
    return mxp;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  //  freopen("medians.in","r",stdin);
  //  freopen("medians.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    mxp=2*n-1;
    upd(1,b[1]);
    upd(3,b[2]);
    if(b[1]<b[2])
    {
        upd(2,f_mx());
    }
    else
    {
        upd(2,f_mi());
    }
    for(int i=3;i<=n;i++)
    {
        int p=2*i-1;
        if(b[i-1]==b[i])
        {
            upd(p-1,f_mi());
            upd(p,f_mx());
        }
        if(b[i-1]<b[i])
        {
            if(viz[b[i]]==0)
            {
                upd(p,b[i]);
                upd(p-1,f_mi());
            }
            else
            {
                upd(p-1,f_mx());
                upd(p,f_mx());
            }
        }
        if(b[i-1]>b[i])
        {
            if(viz[b[i]]==0)
            {
                upd(p,b[i]);
                upd(p-1,f_mx());
            }
            else
            {
                upd(p-1,f_mi());
                upd(p,f_mi());
            }
        }
        ///if(i==5) break;
    }
    for(int i=1;i<=2*n-1;i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<"\n";
    return 0;
}
/**


1     3     3     4     5
1  ?  3  ?  ?  ?  ?  ?  ?
1  9  3  2  4  8  7  5  6


f(i) = i / 2

info (i)
:
 x;
 exista x
 f(i) < x
 f(i) > x


**/

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