Submission #94695

#	Time	Username	Problem	Language	Result	Execution time	Memory
94695		Rouge_Hugo	medians (balkan11_medians)	C++14	100 / 100	54 ms	3780 KiB

medians

#include <bits/stdc++.h>
using namespace std;
vector<int>vv;
int a[100009*2+2];
int v[100009*2+2];

int get (int x)
{
	while (v[x]==1)
	{
		x--;
	}
	v[x]=1;
	return x;
}
int get1 (int x)
{
	while (v[x]==1)
	{
		x++;
	}
	v[x]=1;
	return x;
}

int main()
{
	int l=1;
	
	int n;cin>>n;
	int r=(2*n)-1;
	for(int i=1;i<=n;i++)
	{
		
		cin>>a[i];
		if (i==1)
		{
			v[a[i]]=1;
			vv.push_back(a[i]);
			continue;
		}
		
		if (v[a[i]]==1)
		{
			if (a[i]>a[i-1])
			{
				r=get (r);
				v[r]=1;
				vv.push_back(r);
				
				r=get (r);
				v[r]=1;
				vv.push_back(r);
				}
			else if (a[i]<a[i-1]){
				l=get1 (l);
				v[l]=1;
				vv.push_back(l);
				
				l=get1 (l);
				v[l]=1;
				vv.push_back(l);
				
				
			}
			else {
				l=get1 (l);
				r=get (r);
				v[r]=1;v[l]=1;
				vv.push_back(l);
				vv.push_back(r);
			}
		}
		else {
			if (a[i]>a[i-1])
			{
				v[a[i]]=1;
				r=get (r);
				v[r]=1;
				vv.push_back(a[i]);
				vv.push_back(r);

			}
			else {
				v[a[i]]=1;
				l=get1 (l);
				v[l]=1;
				vv.push_back(a[i]);
				vv.push_back(l);

			}
		}
	}
for(auto pp:vv)cout<<pp<<" ";
 return 0;

}

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