Submission #267991

#	Time	Username	Problem	Language	Result	Execution time	Memory
267991		stefantaga	medians (balkan11_medians)	C++14	100 / 100	83 ms	3576 KiB

medians

#include<bits/stdc++.h>
#define DIM 200005
using namespace std;
int n,i,p,u;
int v[DIM],frec[DIM],sol[DIM];
int main()
{

    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    sol[1]=v[1];
    frec[v[1]]=1;
    p=1;
    u=2*n-1;
    for(i=2; i<=n; i++)
    {
        while(frec[p]==1)
        {
            p++;
        }
        while(frec[u]==1)
        {
            u--;
        }
        if(v[i]==v[i-1])
        {
            sol[2*i-2]=p;
            sol[2*i-1]=u;
            frec[p]=frec[u]=1;
        }
        else
        {
            if(frec[v[i]]==0)
            {
                sol[2*i-2]=v[i];
                frec[v[i]]=1;
                if(v[i]>v[i-1])
                {
                    sol[2*i-1]=u;
                    frec[u]=1;
                }
                else
                {
                    sol[2*i-1]=p;
                    frec[p]=1;
                }
            }
            else
            {
                if(v[i]>v[i-1])
                {
                    sol[2*i-2]=u;
                    frec[u]=1;
                    while(frec[u]==1)
                    {
                        u--;
                    }
                    sol[2*i-1]=u;
                    frec[u]=1;
                }
                else
                {
                    sol[2*i-2]=p;
                    frec[p]=1;
                    while(frec[p]==1)
                    {
                        p++;
                    }
                    sol[2*i-1]=p;
                    frec[p]=1;
                }
            }
        }
    }
    for(i=1; i<=2*n-1; i++)
    {
        cout<<sol[i]<<" ";
    }
    return 0;
}

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