Submission #758560

#	Time	Username	Problem	Language	Result	Execution time	Memory
758560		JellyTheOctopus	medians (balkan11_medians)	C++17	100 / 100	47 ms	2972 KiB

medians

// Balkan Olympiad in Informatics 2011 Day 1 Problem 3
// Medians
// https://oj.uz/problem/view/balkan11_medians

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> A, B;
bool seen[200001];
int minIndex, maxIndex;

int findMax() {
	while (maxIndex >= 1 && seen[maxIndex]) {
		maxIndex--;
	}
	seen[maxIndex] = true;
	return maxIndex;
}

int findMin() {
	while (minIndex <= 2*N-1 && seen[minIndex]) {
		minIndex++;
	}
	seen[minIndex] = true;
	return minIndex;
}

int main() {
	cin >> N;
	B.resize(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> B[i];
	}
	A.push_back(B[1]);
	seen[B[1]] = true;
	minIndex = 1;
	maxIndex = 2*N-1;
	for (int i = 2; i <= N; i++) {
		if (B[i] == B[i-1]) {
			A.push_back(findMax());
			A.push_back(findMin());
		}
		if (B[i] > B[i-1]) {
			A.push_back(findMax());
			if (seen[B[i]]) {
				A.push_back(findMax());
			}
			else {
				A.push_back(B[i]);
				seen[B[i]] = true;
			}
		}
		if (B[i] < B[i-1]) {
			A.push_back(findMin());
			if (seen[B[i]]) {
				A.push_back(findMin());
			}
			else {
				A.push_back(B[i]);
				seen[B[i]] = true;
			}
		}
	}
	for (auto v: A) {
		cout << v << " ";
	} cout << "\n";
}

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