// 23 - 12 - 23
#include<bits/stdc++.h>
using namespace std;
#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"
#define ii pair<int,int>
#define X first
#define Y second
const long long MAX = (int)3e5 + 5;
const long long INF = (int)1e9;
const long long MOD = (int)1e9 + 7;
int n;
int a[MAX],b[MAX];
bool vis[MAX];
// - Lower[i] = i - 1;
// - Upper[i] = 2 * n + 1 - i
//
// // tuc la lower + upper co (2 * i - 2) phan tu.
// (low[i] < bi < upper)
//
// - thg thu i co 2*i - 1 phan tu nen median thu i kh the be hon i - 1 hoac lon hon 2 * n - i + 1
//
// vminx = 1,vmax = 2 * n - 1.
// adding vminx when vminx <= low(i) or vmax when vmax >= upper(i) wont interfere the value of medians after index i
signed main(){
int n;
cin >> n;
int vmin = 1;
int vmax = 2 * n - 1;
for(int i = 1;i <= n;i++){
cin >> b[i];
if(i == 1){
a[i] = b[i];
vis[a[i]] = 1;
continue;
}
if(b[i - 1] == b[i]){
// bi = bi - 1 :
// - gia su (1 -> lower(i)) o trong tap (vmin > lower) -> median b(i - 1) must be (i - 1) ? prove that ?? ( boi vi i - 2 phan tu o trong tap nen phan tu thu i - 1 la i - 1) luon.
// - Nhung bi kh the la i - 1 boi bi i - 1 = lower(i).
// --> cta kh the co bi = b(i -1).
// Vi vay nen cac so tu (1 -> lower(i)) se chua duoc dung trong (2 * (i - 1) - 1) phan tu dau. -> vmin <= lower(i)
while(vis[vmin])++vmin;
a[i * 2 - 2] = vmin;
vis[vmin] = 1;
while(vis[vmax])vmax--;
a[i * 2 - 1] = vmax;
vis[vmax] = 1;
}else if(b[i - 1] > b[i]){
if(!vis[b[i]]){
// 2.1 : bi doesn't appear as median before the index i
// - gia su gia thiet la dung voi i - 1 medians va hi vong no dung voi i medians. -> vmin va vmax != bi.
// thus b(i) kh xuat hien trong (1 -> 2 * (i - 1) - 1) , add vao.
a[i * 2 - 2] = b[i];
vis[b[i]] = 1;
while(vis[vmin])vmin++;
a[i * 2 - 1] = vmin;
vis[vmin] = 1;
}else{
// 2.2 : bi appeared as a median in previous ..
// - luc nay thi tu 1 -> i - 1 chac chan con thieu it nhat la 2 vi tri ?? prove ? neu 1 -> i - 1 deu xuat hien trong premutation thi ? bi > bi + .
// -> add 2 lan vmin
while(vis[vmin])vmin++;
a[i * 2 - 2] = vmin;
vis[vmin] = 1;
while(vis[vmin])vmin++;
a[i * 2 - 1] = vmin;
vis[vmin] = 1;
}
}else{
if(!vis[b[i]]){
a[i * 2 - 2] = b[i];
vis[b[i]] = 1;
while(vis[vmax])vmax--;
a[i * 2 - 1] = vmax;
vis[vmax] = 1;
}else{
while(vis[vmax])vmax--;
a[i * 2 - 1] = vmax;
vis[vmax] = 1;
while(vis[vmax])vmax--;
a[i * 2 - 2] = vmax;
vis[vmax] = 1;
}
}
}
for(int i = 1;i <= 2 * n - 1;i++)cout << a[i] << " \n"[i == 2 * n - 1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
8 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
16 ms |
3676 KB |
Output is correct |
| 7 |
Correct |
25 ms |
4444 KB |
Output is correct |
