답안 #693159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
693159 2023-02-02T12:27:14 Z Doncho_Bonboncho 중앙값 배열 (balkan11_medians) C++14
0 / 100
24 ms 3156 KB
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
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++ ) std::cout<<nas[i]<<" ";
	std::cout<<"\n";


	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 19]
2 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 39]
3 Incorrect 0 ms 212 KB Integer 0 violates the range [1, 59]
4 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 79]
5 Incorrect 1 ms 212 KB Integer 0 violates the range [1, 99]
6 Incorrect 0 ms 212 KB Integer 0 violates the range [1, 119]
7 Incorrect 0 ms 212 KB Integer 0 violates the range [1, 139]
8 Incorrect 1 ms 340 KB Integer 0 violates the range [1, 159]
9 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 179]
10 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 199]
11 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 599]
12 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 1199]
13 Incorrect 1 ms 340 KB Integer 0 violates the range [1, 1999]
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Integer 0 violates the range [1, 3999]
2 Incorrect 2 ms 340 KB Integer 0 violates the range [1, 7999]
3 Incorrect 2 ms 468 KB Integer 0 violates the range [1, 15999]
4 Incorrect 4 ms 688 KB Integer 0 violates the range [1, 31999]
5 Incorrect 8 ms 1236 KB Integer 0 violates the range [1, 63999]
6 Incorrect 15 ms 2104 KB Integer 0 violates the range [1, 127999]
7 Incorrect 24 ms 3156 KB Integer 0 violates the range [1, 199999]