#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
int n, b[N], a[N];
int bit[N];
void up(int x) {
for (; x <= 300000; x += x& - x) bit[x] += 1;
}
int get(int x) {
int ans = 0;
for (; x > 0; x -= x& - x) ans += bit[x];
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin >> n;
memset(bit, 0, sizeof bit);
for (int i = 1; i <= n; i++) cin >> b[i];
set <int> s;
for (int i = 1; i <= 2 * n - 1; i++) s.insert(i);
a[1] = b[1];
s.erase(a[1]);
up(a[1]);
int j = 2;
for (int i = 2; i <= n; i++) {
int small = get(b[i] - 1);
int large = get(2 * n - 1) - get(b[i]);
int balance = i - 1;
if (s.find(b[i]) != s.end()) {
up(b[i]);
s.erase(b[i]);
a[j] = b[i];
j++;
}
while (small < balance) {
a[j] = *s.begin();
up(a[j]);
s.erase(a[j]);
j++;
small++;
}
while (large < balance) {
a[j] = *s.rbegin();
up(a[j]);
s.erase(a[j]);
j++;
large++;
}
}
for (int i = 1; i <= n * 2 - 1; i++) cout << a[i] << " ";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |