#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
const int N = 2e5 + 50;
int seg[4*N];
int n;
int b[N];
vector<int> a;
void update(int node, int l, int r, int pos)
{
if(l==r){
seg[node] = 1;
return;
}
int mid = (l+r)/2;
if(pos>mid) update(node*2+2, mid+1, r, pos);
else update(node*2+1, l, mid, pos);
seg[node] = seg[node*2+1] + seg[node*2+2];
}
int get_sum(int node, int l, int r, int i, int j)
{
if(i>r||j<r) return 0;
if(i>=l&&j<=r) return seg[node];
int mid = (i+j)/2;
return get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
}
int main()
{
ios
cin>>n;
for(int i = 0;i<n;i++) cin>>b[i];
update(0, 0, 2*n, b[0]);
a.pb(b[0]);
int l = 1;
if(b[0]==1) l++;
int r = 2*n-1;
if(b[0]==2*n-1) r--;
for(int i = 1;i<n;i++)
{
int x = b[i];
int cl = get_sum(0, 0, x-1, 0, 2*n);
int cr = get_sum(0, x+1, 2*n, 0, 2*n);
while(get_sum(0, l, l, 0, 2*n)) l++;
while(get_sum(0, r, r, 0, 2*n)) r--;
if(l==x) l++;
if(r==x) r--;
//cout<<cl<<" "<<cr<<" ";
if(cl==cr)
{
//cout<<i<<" 1"<<endl;
while(get_sum(0, l, l, 0, 2*n)) l++;
while(get_sum(0, r, r, 0, 2*n)) r--;
a.pb(l);
a.pb(r);
update(0, 0, 2*n, l);
update(0, 0, 2*n, r);
l++;
r--;
while(get_sum(0, l, l, 0, 2*n)) l++;
while(get_sum(0, r, r, 0, 2*n)) r--;
}
else if(cl>cr)
{
if(!get_sum(0, x, x, 0, 2*n))
{
//cout<<i<<" 2"<<endl;
while(get_sum(0, l, l, 0, 2*n)) l++;
while(get_sum(0, r, r, 0, 2*n)) r--;
a.pb(x);
a.pb(r);
update(0, 0, 2*n, x);
update(0, 0, 2*n, r);
r--;
while(get_sum(0, r, r, 0, 2*n)) r--;
}
else
{
//cout<<i<<" 3"<<endl;
while(get_sum(0, l, l, 0, 2*n)) l++;
while(get_sum(0, r, r, 0, 2*n)) r--;
a.pb(r);
update(0, 0, 2*n, r);
r--;
while(get_sum(0, r, r, 0, 2*n)) r--;
update(0, 0, 2*n, r);
a.pb(r);
r--;
while(get_sum(0, r, r, 0, 2*n)) r--;
}
}
else
{
if(!get_sum(0, x, x, 0, 2*n))
{
//cout<<i<<" 4"<<endl;
while(get_sum(0, l, l, 0, 2*n)) l++;
while(get_sum(0, r, r, 0, 2*n)) r--;
a.pb(x);
a.pb(l);
update(0, 0, 2*n, x);
update(0, 0, 2*n, l);
l++;
while(get_sum(0, l, l, 0, 2*n)) l++;
}
else
{
//cout<<i<<" 5"<<endl;
while(get_sum(0, l, l, 0, 2*n)) l++;
while(get_sum(0, r, r, 0, 2*n)) r--;
a.pb(l);
update(0, 0, 2*n, l);
l++;
while(get_sum(0, l, l, 0, 2*n)) l++;
update(0, 0, 2*n, l);
a.pb(l);
l++;
while(get_sum(0, l, l, 0, 2*n)) l++;
}
}
}
for(int x : a)
cout<<x<<" ";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 11 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output isn't correct |
| 2 |
Incorrect |
7 ms |
492 KB |
Output isn't correct |
| 3 |
Incorrect |
11 ms |
748 KB |
Output isn't correct |
| 4 |
Incorrect |
23 ms |
1132 KB |
Output isn't correct |
| 5 |
Incorrect |
48 ms |
1900 KB |
Output isn't correct |
| 6 |
Incorrect |
100 ms |
3048 KB |
Output isn't correct |
| 7 |
Incorrect |
167 ms |
5068 KB |
Output isn't correct |
