Submission #1171949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171949		nuutsnoynton	medians (balkan11_medians)	C++20	5 / 100	56 ms	32836 KiB

medians

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 2e5 + 2;
set < ll > uragsh_ind[N], aragsh_ind[N];
ll uragsh[N], aragsh[N], a[N], b[N], used[N];
int main() {
	ll n, m, r, x,s, y, i, j,ind, ans, t;
	
	cin >> n;
	
	
	
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	used[a[1]] = 1;
	for (i = 1; i <= 2 * n - 1; i ++) b[i]= -1;
	b[1] = a[1];
	for (i = 2; i <= n; i ++) {
		if ( a[i] == a[i - 1]) {
			uragsh[a[i]] = aragsh[a[i]] = 1;
			uragsh_ind[a[i]].insert(i);
			aragsh_ind[a[i]].insert(i);
		}
		else {
			if ( a[i] > a[i- 1]) {
				aragsh_ind[a[i]].insert(i);
				aragsh[a[i]] =1;
				used[a[i]] = 1;
				b[2 * i - 1] = a[i];
			}
			else {
				uragsh_ind[a[i]].insert(i);
				used[a[i]] = 1;
				uragsh[a[i]] = 1;
				b[2 * i - 1] = a[i];
			}
		}
	}
	queue < ll > q;
	for (i =1 ; i <= 2 *n - 1; i ++) {
		for ( ll ind : uragsh_ind[i]) {
			s = q.front();
			used[s] = 1;
			q.pop();
			b[ind * 2 - 2] = s;
		}	
		if ( uragsh_ind[i].empty() && aragsh_ind[i].empty())q.push(i);
	}
	queue < ll > v;
	for (i = 2 * n - 1; i >= 1; i --) {
		for ( ll ind : aragsh_ind[i]) {
			s = v.front();
			v.pop();
			//ind =-ind;
			if ( b[ind * 2 - 1] == -1) b[ind * 2 - 1] = s;
			else b[ind * 2 - 2] = s;
		}
		if ( uragsh_ind[i].empty() && aragsh_ind[i].empty())v.push(i);
	}
//	for (i = 1; i <= 2 * n - 1; i ++) {
//		for (j = i + 1; j <= 2 * n - 1; j ++) {
//			if ( b[i] == b[j]) {
//				while(1);
//			}
//		}
//	}
	for (i = 1; i <= 2 *n - 1; i ++) {
		if ( b[i] < 1 || b[i] > 2 * n - 1) {
			while(1);
		}
		cout << b[i] << " ";
	}
	cout <<"\n";
}

• Subtask 1: 5 / 65
• Subtask 2: 0 / 35