Submission #39703

#	Time	Username	Problem	Language	Result	Execution time	Memory
39703		Pajaraja	medians (balkan11_medians)	C++14	100 / 100	69 ms	7872 KiB

medians

#include <bits/stdc++.h>
using namespace std;
bool u[200007],k[200007];
int b[100007],add;
vector<int> ub[100007];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%d",&b[i]);
	priority_queue<int> g,l;
	//for(int i=0;i<n-1;i++) for(int j=fmin(b[i],b[i+1]);j<fmax(b[i],b[i+1]);j++) k[j]=true;
	for(int i=1;i<2*n;i++) if(!k[i])
	{
		g.push(i);
		l.push(-i);
	} 
	u[b[0]]=true;
	add=1;
	printf("%d ",b[0]);
	for(int i=0;i<n-1;i++)
	{
		if(!u[b[i+1]])
		{
		    u[b[i+1]]=true;
	        add++;
	        printf("%d ",b[i+1]);
		}
		if(b[i]>b[i+1])
		{
			while(add<2*i+3)
			{
				int c=-l.top();
				l.pop();
				if(u[c]) continue;
				u[c]=true;
	            add++;
	            printf("%d ",c);
			}
		}
		if(b[i]==b[i+1])
		{
			while(add<2*i+2)
			{
				int c=-l.top();
				l.pop();
				if(u[c]) continue;
				u[c]=true;
	            add++;
	            printf("%d ",c);
			}
			while(add<2*i+3)
			{
				int c=g.top();
				g.pop();
				if(u[c]) continue;
				u[c]=true;
	            add++;
	            printf("%d ",c);
			}
		}
		if(b[i]<b[i+1])
		{
			while(add<2*i+3)
			{
				int c=g.top();
				g.pop();
				if(u[c]) continue;
				u[c]=true;
	            add++;
	            printf("%d ",c);
			}
		}
		/*for(int j=fmin(b[i],b[i+1]);j<fmax(b[i],b[i+1]);j++)
		{
		    g.push(j);
		    l.push(-j);	
		}*/
	}
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:9:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
medians.cpp:10:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<n;i++) scanf("%d",&b[i]);
                                        ^

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