oj.uz

답안 #693164

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

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


	return 0;
}

Subtask #1
0.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Runtime error 1 ms 468 KB Execution killed with signal 6
7 Runtime error 1 ms 468 KB Execution killed with signal 6
8 Runtime error 1 ms 468 KB Execution killed with signal 6
9 Runtime error 1 ms 468 KB Execution killed with signal 6
10 Runtime error 1 ms 468 KB Execution killed with signal 6
11 Runtime error 1 ms 468 KB Execution killed with signal 6
12 Runtime error 1 ms 468 KB Execution killed with signal 6
13 Runtime error 1 ms 468 KB Execution killed with signal 6

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Runtime error 1 ms 596 KB Execution killed with signal 6
3 Runtime error 2 ms 724 KB Execution killed with signal 6
4 Runtime error 2 ms 980 KB Execution killed with signal 6
5 Runtime error 4 ms 1540 KB Execution killed with signal 6
6 Runtime error 7 ms 2488 KB Execution killed with signal 6
7 Runtime error 12 ms 3796 KB Execution killed with signal 6