답안 #758559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
758559 2023-06-14T22:08:28 Z JellyTheOctopus 중앙값 배열 (balkan11_medians) C++17
10 / 100
43 ms 3248 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());
			B.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";
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
2 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
5 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
8 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
9 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
10 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
11 Incorrect 0 ms 212 KB Unexpected end of file - int32 expected
12 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
13 Incorrect 1 ms 212 KB Unexpected end of file - int32 expected
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
2 Incorrect 2 ms 340 KB Unexpected end of file - int32 expected
3 Incorrect 3 ms 468 KB Unexpected end of file - int32 expected
4 Incorrect 7 ms 724 KB Unexpected end of file - int32 expected
5 Incorrect 16 ms 1188 KB Unexpected end of file - int32 expected
6 Incorrect 30 ms 1996 KB Unexpected end of file - int32 expected
7 Incorrect 43 ms 3248 KB Unexpected end of file - int32 expected