2015
07-16

# IT Companies

There are N IT companies which are labeled from 1 to N. Each of them has a branch (a branch is not a company, and companies and branches are all called "unit").The branches are labeled from -1 to �CN. The branch of company i is labeled as -i. The number of workers of each company and its branch has to fit the rules below:
1. The number of workers of a company must be larger than that of the branch of it.
2. There are more workers in company i than company j if and only if there are more workers in the branch of company i than the branch of company j.
Among the companies whose label is larger than i（range from i+1 to n）,and the branches whose label is larger than -i (range from -1 to �C(i-1) ), there are c[i] units which have more workers than company i.
You need to sort the 2×N units in the ascending order by the number of workers.

The input contains multiple test cases. Each test case begins with a single line containing one integer N indicating the number of companies (0 < N ≤ 100000). Next line contains N integers which are c[1],c[2]…c[N] (c[i] ≤ N).
The input ends with N = 0.

The input contains multiple test cases. Each test case begins with a single line containing one integer N indicating the number of companies (0 < N ≤ 100000). Next line contains N integers which are c[1],c[2]…c[N] (c[i] ≤ N).
The input ends with N = 0.

2
1 1
10
4 8 3 4 2 0 5 7 1 6
0

Impossible
-8 -2 -10 -7 8 2 10 -4 7 -1 4 -3 -5 -9 1 3 5 9 -6 6

1．一开始开2个队列a,ba为答案队列，b为临时队列

2．找出当最小的C值为C[k]（相同时取k最小的）

a)C[k]=0：将k加入a-k加入b。在C序列中删除元素C[k]，并将C[1]C[k-1]减一。

b)C[k]>0：将b队首的元素p取出加入a，并将C[-p+1]c[n]减一。

3．将b接在a后面，倒序就是答案序列

1C中出现了负数。

2．出现2b情况时b为空

#include <iostream>
#include <cstdio>
#include <cstring>
#define ls (t<<1)
#define rs (t<<1|1)
#define midt (tr[t].l+tr[t].r>>1)
using namespace std;
const int maxn=1e5+9;
const int inf=1111111;
int ans[maxn<<1],que[maxn<<1];
int a[maxn];

struct
{
int l,r,min,lazy,id;
}tr[maxn<<2];

void pushdown(int t)
{
if(tr[t].lazy)
{
tr[ls].min+=tr[t].lazy;
tr[rs].min+=tr[t].lazy;
tr[ls].lazy+=tr[t].lazy;
tr[rs].lazy+=tr[t].lazy;
tr[t].lazy=0;
}
}

void maketree(int t,int l,int r)
{
tr[t].l=l;
tr[t].r=r;
tr[t].lazy=0;
if(l==r)
{
tr[t].min=a[l];
tr[t].id=l;
return ;
}
int mid=midt;
maketree(ls,l,mid);
maketree(rs,mid+1,r);
if(tr[ls].min<=tr[rs].min)
{
tr[t].min=tr[ls].min;
tr[t].id=tr[ls].id;
}
else
{
tr[t].min=tr[rs].min;
tr[t].id=tr[rs].id;
}
}

void modify(int t,int l,int r,int tmp)
{
if(tr[t].l==l&&tr[t].r==r)
{
tr[t].min+=tmp;
tr[t].lazy+=tmp;
return ;
}
pushdown(t);
int mid=midt;
if(r<=mid) modify(ls,l,r,tmp);
else if(mid+1<=l) modify(rs,l,r,tmp);
else
{
modify(ls,l,mid,tmp);
modify(rs,mid+1,r,tmp);
}

if(tr[ls].min<=tr[rs].min)
{
tr[t].min=tr[ls].min;
tr[t].id=tr[ls].id;
}
else
{
tr[t].min=tr[rs].min;
tr[t].id=tr[rs].id;
}
}

int querymin()
{
//    cout<<tr[1].min<<endl;
if(tr[1].min==0)
return tr[1].id;
else return -1;
}

int main()
{
int n;
while(scanf("%d",&n),n)
{
int st=1,ed=0,lon=2*n;
bool flage=1;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
maketree(1,1,n);
for(int i=1;i<=n;i++)
{
int tmp;
while(querymin()==-1)
{
if(st<=ed)
{
ans[lon--]=-que[st];
if(que[st]+1<=n)
modify(1,que[st]+1,n,-1);
st++;
}
else
{
flage=0;
break;
}
}
if(!flage) break;
tmp=querymin();
ans[lon--]=tmp;
que[++ed]=tmp;
if(1<=tmp-1)
modify(1,1,tmp-1,-1);
modify(1,tmp,tmp,inf);
}
if(!flage)
{
printf("Impossible\n");
}
else
{
while(st<=ed)
{
ans[lon--]=-que[st++];
}
for(int i=1;i<=n*2;i++)
printf("%d ",ans[i]);
printf("\n");
}
}
return 0;
}