#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 100000 + 5;
int n;
int a[N];
int b[N];
bool vis[N];
void solve() {
a[1] = b[1]; vis[b[1]] = true;
int L = 1, R = 2 * n - 1;
for(int i = 2; i <= n; i++) {
int l = 2 * i - 2;
int r = 2 * i - 1;
if(b[i - 1] == b[i]) {
while(vis[L]) L += 1;
a[l] = L; vis[L] = true;
while(vis[R]) R -= 1;
a[r] = R; vis[R] = true;
}
else if(b[i - 1] > b[i]) {
if(not vis[b[i]]) {
a[l] = b[i]; vis[b[i]] = true;
while(vis[L]) L += 1;
a[r] = L; vis[L] = true;
}
else {
while(vis[L]) L += 1;
a[l] = L; vis[L] = true;
while(vis[L]) L += 1;
a[r] = L; vis[L] = true;
}
}
else {
if(not vis[b[i]]) {
a[l] = b[i]; vis[b[i]] = true;
while(vis[R]) R -= 1;
a[r] = R; vis[R] = true;
}
else {
while(vis[R]) R -= 1;
a[l] = R; vis[R] = true;
while(vis[R]) R -= 1;
a[r] = R; vis[R] = true;
}
}
}
}
int main() {
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) cin >> b[i];
solve();
for(int i = 1; i <= 2 * n - 1; i++) cout << a[i] << " \n"[i == 2 * n - 1];
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
464 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
472 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
3 ms |
604 KB |
Output is correct |
4 |
Correct |
3 ms |
860 KB |
Output is correct |
5 |
Correct |
5 ms |
1116 KB |
Output is correct |
6 |
Correct |
10 ms |
2072 KB |
Output is correct |
7 |
Correct |
16 ms |
2904 KB |
Output is correct |