oj.uz

Submission #119943

# Submission time Handle Problem Language Result Execution time Memory
119943 2019-06-22T17:09:16 Z tutis medians (balkan11_medians) C++17
100 / 100
 104 ms 12240 KB 
/*input
5
1 3 3 4 5
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	int m[n];
	for (int i = 0; i < n; i++)
		cin >> m[i];
	set<int>nebus;
	for (int i = 1; i <= 2 * n - 1; i++)
		nebus.insert(i);
	for (int i = 0; i < n; i++)
		nebus.erase(m[i]);
	deque<int>answer;
	int p[2 * n];
	fill_n(p, 2 * n, n + 10);
	for (int i = 0; i < n; i++)
		p[m[i]] = min(p[m[i]], i);
	for (int i = n - 1; i > 0; i--)
	{
		if (p[m[i]] == i)
			nebus.insert(m[i]);
		if (m[i] == m[i - 1])
		{
			auto it = nebus.lower_bound(m[i]);
			assert(it != nebus.end());
			answer.push_front(*it);
			nebus.erase(it);
			it = nebus.upper_bound(m[i]);
			assert(it != nebus.begin());
			it--;
			answer.push_front(*it);
			nebus.erase(it);
		}
		else
		{
			if (m[i] > m[i - 1])
			{
				auto it = nebus.lower_bound(m[i]);
				assert(it != nebus.end());
				answer.push_front(*it);
				nebus.erase(it);
				it = nebus.lower_bound(m[i]);
				assert(it != nebus.end());
				answer.push_front(*it);
				nebus.erase(it);
			}
			else
			{
				auto it = nebus.upper_bound(m[i]);
				assert(it != nebus.begin());
				it--;
				answer.push_front(*it);
				nebus.erase(it);
				it = nebus.upper_bound(m[i]);
				assert(it != nebus.begin());
				it--;
				answer.push_front(*it);
				nebus.erase(it);
			}
		}
	}
	nebus.insert(m[0]);
	assert(nebus.size() == 1);
	answer.push_front(*nebus.begin());
	for (int i : answer)
		cout << i << " ";
}

Subtask #1
65.0 / 65.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 5 ms 868 KB Output is correct
3 Correct 8 ms 1252 KB Output is correct
4 Correct 14 ms 2336 KB Output is correct
5 Correct 29 ms 4216 KB Output is correct
6 Correct 61 ms 7992 KB Output is correct
7 Correct 104 ms 12240 KB Output is correct