oj.uz

Submission #18404

# Submission time Handle Problem Language Result Execution time Memory
18404 2016-01-31T08:19:20 Z choyi0521 medians (balkan11_medians) C++
100 / 100
 119 ms 12236 KB 
#include<set>
#include<stdio.h>
using namespace std;
const int MAX_N = 100000;
set<int> st;
int n, a[MAX_N], cnt[MAX_N * 2], res[MAX_N * 2], p;
void d(int x){
	set<int>::iterator it = st.upper_bound(x);
	res[--p] = *--it;
	st.erase(res[p]);
}
void u(int x){
	res[--p] = *st.upper_bound(x);
	st.erase(res[p]);
}
int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
		cnt[a[i]]++;
	}
	for (int i = 1; i < 2 * n; i++)
		if (!cnt[i]) st.insert(i);
	p = 2 * n - 1;
	for (int i = n - 2; i >= 0; i--){
		if (!--cnt[a[i + 1]]) st.insert(a[i + 1]);
		if (a[i] < a[i + 1]){
			u(a[i]);
			u(a[i]);
		}
		else if (a[i]>a[i + 1]){
			d(a[i]);
			d(a[i]);
		}
		else d(a[i]), u(a[i]);
	}
	res[0] = a[0];
	for (int i = 0; i < 2 * n - 1; i++)
		printf("%d ", res[i]);
	return 0;
}

Compilation message

medians.cpp: In function 'int main()':
medians.cpp:17:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
medians.cpp:19:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
                     ^

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3260 KB Output is correct
2 Correct 3 ms 3524 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 13 ms 4580 KB Output is correct
5 Correct 33 ms 6032 KB Output is correct
6 Correct 66 ms 8936 KB Output is correct
7 Correct 119 ms 12236 KB Output is correct