oj.uz

Submission #758560

# Submission time Handle Problem Language Result Execution time Memory
758560 2023-06-14T22:09:43 Z JellyTheOctopus medians (balkan11_medians) C++17
100 / 100
 47 ms 2972 KB 
// 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.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 8 ms 860 KB Output is correct
5 Correct 15 ms 1232 KB Output is correct
6 Correct 29 ms 2044 KB Output is correct
7 Correct 47 ms 2972 KB Output is correct