Submission #693164

#	Time	Username	Problem	Language	Result	Execution time	Memory
693164		Doncho_Bonboncho	medians (balkan11_medians)	C++14	0 / 100	12 ms	3796 KiB

medians

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6 + 42;
const int INF = 1e9;
const int mod = 1e9 + 7;

int a[MAX_N];
int nas[MAX_N];

int maxInd;
int minInd;

bool viz[MAX_N];

int n;

void updateMin( ){
	while( minInd < 2*n and viz[minInd] ) minInd ++;
}

void updateMax( ){
	while( maxInd > 0 and viz[maxInd] ) maxInd --;
}
int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	//freopen( "medians.in", "r", stdin );
	//freopen( "medians.out", "w", stdout );


	std::cin>>n;
	for( int i=0 ; i<n ; i++ ) std::cin>>a[i];
	
	nas[0] = a[0];
	viz[a[0]] = true;

	maxInd = 2*n;
	minInd = 0;
	viz[0] = true;
	viz[2*n] = true;
	
	updateMax();
	updateMin();

	for( int i=1 ; i<n ; i++ ){
		if( a[i] == a[i-1] ){
			updateMax();
			nas[i*2 -1] = maxInd;
			viz[maxInd] = true;

			updateMin();
			nas[i*2] = minInd;
			viz[minInd] = true;

		}else{
			if( a[i] > a[i-1] ){
				if( !viz[a[i]] ){
					nas[i*2 -1] = a[i];
					viz[a[i]] = true;
					updateMax();
					nas[i*2] = maxInd;
					viz[maxInd] = true;
	
				}else{
					updateMax();
					nas[i*2 -1] = maxInd;
					viz[maxInd] = true;

					updateMax();
					nas[i*2] = maxInd;
					viz[maxInd] = true;
				}
			}else{

				if( !viz[a[i]] ){
					nas[i*2 -1] = a[i];
					viz[a[i]] = true;

					updateMin();
					a[i*2] = minInd;
					viz[minInd] = true;

				}else{
					updateMin();
					nas[i*2 - 1] = minInd;
					viz[minInd] = true;

					updateMin();
					nas[i*2] = minInd;
					viz[minInd] = true;
				}
			}
		}
		updateMax();
		updateMin();
	}

	for( int i=0 ; i<2*n -1 ; i++ ){
		assert( nas[i] > 0 );
		std::cout<<nas[i]<<" ";
	}
	std::cout<<"\n";


	return 0;
}

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