Submission #1171970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171970		nuutsnoynton	medians (balkan11_medians)	C++20	5 / 100	68 ms	13384 KiB

medians

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e5 + 2;
ll used[N] = {0};
multiset < ll > S;
void remove_max() {
	auto R = S.end();
	R --;
	S.erase(R);
	return ;
}
ll find_max() {
	auto R = S.end();
	R --;
	used[*R] = 1;
	return (*R);
}
void remove_min() {
	auto R = S.begin();
	S.erase(R);
	return ;
}
ll find_min() {
	auto R = S.begin();
	used[*R] = 1;
	return (*R);
}
int main() {
	ll n, m, r, x,s, y, i, j,ind, t;
	
	cin >> n;
	
	
	ll a[n + 2];
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for (i = 1; i <= 2 * n - 1; i ++) S.insert(i);
	vector < ll > ans;
	ans.push_back(a[1]);
	used[a[1]]= 1;
	S.erase(S.find(a[1]));
	for (i = 2; i <= n; i ++) {
		if ( a[i] == a[i - 1]) {
			ans.push_back(find_max());
			ans.push_back(find_min());
			remove_max();
			remove_min();
		} 
		else {
			if ( a[i] > a[i- 1]) {
				if ( used[a[i]] == 1) {
					ans.push_back(find_min());
					remove_min();
					ans.push_back(find_min());
					remove_min();
				}
				else {
					ans.push_back(a[i]);
					S.erase(S.find(a[i]));
					ans.push_back(find_min());
					remove_min();
				}
			}
			else {
				if ( used[a[i]] == 1) {
					ans.push_back(find_max());
					remove_max();
					ans.push_back(find_max());
					remove_max();
				}
				else {
					ans.push_back(a[i]);
					S.erase(S.find(a[i]));
					ans.push_back(find_max());
					remove_max();
				}
			}
			
			
		}
	//	cout << i << "HI"<< endl;
		used[a[i]] = 1;
	}
	for ( ll X : ans) cout <<X << " ";
	
}

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