Submission #18404

#	Time	Username	Problem	Language	Result	Execution time	Memory
18404		choyi0521	medians (balkan11_medians)	C++98	100 / 100	119 ms	12236 KiB

medians

#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 (stderr)

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 / 65
• Subtask 2: 35 / 35