oj.uz

답안 #94695

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94695 2019-01-22T20:11:29 Z Rouge_Hugo 중앙값 배열 (balkan11_medians) C++14
100 / 100
 54 ms 3780 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int>vv;
int a[100009*2+2];
int v[100009*2+2];

int get (int x)
{
	while (v[x]==1)
	{
		x--;
	}
	v[x]=1;
	return x;
}
int get1 (int x)
{
	while (v[x]==1)
	{
		x++;
	}
	v[x]=1;
	return x;
}

int main()
{
	int l=1;
	
	int n;cin>>n;
	int r=(2*n)-1;
	for(int i=1;i<=n;i++)
	{
		
		cin>>a[i];
		if (i==1)
		{
			v[a[i]]=1;
			vv.push_back(a[i]);
			continue;
		}
		
		if (v[a[i]]==1)
		{
			if (a[i]>a[i-1])
			{
				r=get (r);
				v[r]=1;
				vv.push_back(r);
				
				r=get (r);
				v[r]=1;
				vv.push_back(r);
				}
			else if (a[i]<a[i-1]){
				l=get1 (l);
				v[l]=1;
				vv.push_back(l);
				
				l=get1 (l);
				v[l]=1;
				vv.push_back(l);
				
				
			}
			else {
				l=get1 (l);
				r=get (r);
				v[r]=1;v[l]=1;
				vv.push_back(l);
				vv.push_back(r);
			}
		}
		else {
			if (a[i]>a[i-1])
			{
				v[a[i]]=1;
				r=get (r);
				v[r]=1;
				vv.push_back(a[i]);
				vv.push_back(r);

			}
			else {
				v[a[i]]=1;
				l=get1 (l);
				v[l]=1;
				vv.push_back(a[i]);
				vv.push_back(l);

			}
		}
	}
for(auto pp:vv)cout<<pp<<" ";
 return 0;

}

Subtask #1
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 2 ms 252 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 376 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 18 ms 1396 KB Output is correct
6 Correct 33 ms 2416 KB Output is correct
7 Correct 54 ms 3780 KB Output is correct