#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5 + 5;
int seg[N * 4];
void Upd(int l, int r, int pos, int qpos) {
if(l == r) {
seg[pos]++;
return;
}
int mid = (l + r) >> 1;
if(qpos <= mid) Upd(l, mid, pos * 2, qpos);
else Upd(mid + 1, r, pos * 2 + 1, qpos);
seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}
int Query(int l, int r, int pos, int ql, int qr) {
if(ql <= l && r <= qr) {
return seg[pos];
}
if(ql > r || l > qr) {
return 0;
}
int mid = (l + r) >> 1;
return Query(l, mid, pos * 2, ql, qr) + Query(mid + 1, r, pos * 2 + 1, ql, qr);
}
void Solve() {
int n;
cin >> n;
int b[n + 1];
for(int i = 1; i <= n; i++) {
cin >> b[i];
}
int a[n * 2 + 1];
set<int> s;
for(int i = 1; i < 2 * n; i++) {
s.insert(i);
}
for(int i = 1; i < n * 2; i++) {
a[i] = 0;
}
vector<int> ans;
ans.push_back(b[1]);
a[b[1]] = 1;
s.erase(b[1]);
//cout << "first val = " << b[1] << endl;
Upd(1, 2 * n - 1, 1, b[1]);
for(int i = 2; i <= n; i++) {
//cout << "i = " << i << endl;
if(a[b[i]] == 1) {
int ans1 = Query(1, 2 * n - 1, 1, 1, b[i] - 1), ans2 = Query(1, 2 * n - 1, 1, b[i] + 1, 2 * n - 1);
assert(abs(ans1 - ans2) == 2 || ans1 == ans2);
//cout << "ans1 = " << ans1 << ", ans2 = " << ans2 << "\n";
int st = ((ans1 - ans2) == -2) ? 2 : ((ans1 - ans2 == 0) ? 1 : 0);
int en = ((ans1 - ans2) == 2) ? 2 : ((ans1 - ans2 == 0) ? 1 : 0);
while(st != 0) {
auto f = s.begin();
s.erase(*f);
ans.push_back(*f);
a[*f] = 1;
Upd(1, 2 * n - 1, 1, *f);
//cout << "val = " << *f << endl;
st--;
}
while(en != 0) {
auto f = --s.end();
s.erase(*f);
ans.push_back(*f);
a[*f] = 1;
Upd(1, 2 * n - 1, 1, *f);
//cout << "value = " << *f << endl;
en--;
}
}
else {
ans.push_back(b[i]);
a[b[i]] = 1;
//cout << "Upd value = " << b[i] << endl;
s.erase(b[i]);
Upd(1, 2 * n - 1, 1, b[i]);
int ans1 = Query(1, 2 * n - 1, 1, 1, b[i] - 1), ans2 = Query(1, 2 * n - 1, 1, b[i] + 1, 2 * n - 1);
assert(abs(ans1 - ans2) == 1);
if(ans1 < ans2) {
auto f = s.begin();
s.erase(*f);
ans.push_back(*f);
a[*f] = 1;
//cout << "Val = " << *f << endl;
Upd(1, 2 * n - 1, 1, *f);
}
else {
auto f = --s.end();
s.erase(*f);
ans.push_back(*f);
a[*f] = 1;
//cout << "Value = " << *f << endl;
Upd(1, 2 * n - 1, 1, *f);
}
}
}
for(int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
cout << "\n";
}
int32_t main() {
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Compilation message
medians.cpp: In function 'void Solve()':
medians.cpp:106:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
106 | for(int i = 0; i < ans.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Integer 400 violates the range [1, 99] |
| 6 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 9 |
Incorrect |
0 ms |
332 KB |
Not a permutation |
| 10 |
Incorrect |
1 ms |
332 KB |
Not a permutation |
| 11 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
1 ms |
716 KB |
Execution killed with signal 6 |
| 13 |
Runtime error |
1 ms |
716 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1100 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
3 ms |
1612 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
5 ms |
2636 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
13 ms |
4868 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
23 ms |
9044 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
37 ms |
16532 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
70 ms |
24928 KB |
Execution killed with signal 6 |
