IT Companies

Question

Problem Description
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 –N. 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 –(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.

Input
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]…cN.
The input ends with N = 0.

Output
For each test case, output the sorted label sequence of all units in a line. If there are no solutions, output "Impossible" instead.
This problem is special judged.

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

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

Answer 1

#include
#include
#include
#include
using namespace std;
const int N = 100005;
const int INF = 0x3f3f3f3f;

struct node
{
int lazy,mn;
}tree[N<<2];
int n;
int pos;
bool flag;
int que1[N + N],que2[N + N];
int h1,h2,t1,t2;

int Min(int a,int b)
{
return a > b ? b:a;
}

void build(int num,int s,int e)
{
tree[num].lazy = tree[num].mn = 0;
if(s == e)
{
scanf("%d",&tree[num].mn);
return;
}
int mid = (s + e)>>1;
build(num<<1,s,mid);
build(num<<1|1,mid + 1,e);
tree[num].mn = Min(tree[num<<1].mn,tree[num<<1|1].mn);
}

void insert(int num,int s,int e,int l,int r)
{
if(l > r)
return;
if(s == l && e == r)
{
tree[num].lazy --;
return;
}
if(tree[num].lazy != 0)
{
tree[num< tree[num tree[num].mn += tree[num].lazy;
tree[num].lazy = 0;
}
int mid = (s + e)>>1;
if(r <= mid)
insert(num< else
{
if(l > mid)
insert(num<<1|1,mid + 1,e,l,r);
else
{
insert(num<<1,s,mid,l,mid);
insert(num<<1|1,mid + 1,e,mid + 1,r);
}
}
tree[num].mn = Min(tree[num<<1].lazy + tree[num<<1].mn,tree[num<<1|1].lazy + tree[num<<1|1].mn);
}

void query(int num,int s,int e)
{
if(s == e)
{
pos = s;
if(tree[num].mn + tree[num].lazy == 0)
tree[num].mn = INF;
return ;
}
if(tree[num].lazy != 0)
{
tree[num< tree[num tree[num].mn += tree[num].lazy;
tree[num].lazy = 0;
}
int mid = (s + e)>>1;
if(tree[num<<1].mn + tree[num<<1].lazy <= tree[num<<1|1].lazy + tree[num<<1|1].mn)
query(num<<1,s,mid);
else
query(num<<1|1,mid + 1,e);
tree[num].mn = Min(tree[num<<1].lazy + tree[num<<1].mn,tree[num<<1|1].lazy + tree[num<<1|1].mn);
}

void solve()
{
while(t1 - h1 != n + n)
{
while(tree[1].mn == 0)
{
query(1,1,n);
que1[t1 ++] = pos;
que2[t2 ++] = -pos;
insert(1,1,n,1,pos - 1);
}
if(tree[1].mn < 0)//当前最小rank为负，不科学，无解
{
flag = false;
return;
}
while(tree[1].mn > 0)
{
if(h2 >= t2)
{
if(tree[1].mn > N)//找完了
return;
flag = false;//没找完，但是que2中没有元素了，也就是说
return;//当前rank没有为0的，不科学，无解
}
que1[t1 ++] = que2[h2];
insert(1,1,n,1 - que2[h2 ++],n);
}
}
}

int main()
{
int i,j;
while(scanf("%d",&n),n)
{
build(1,1,n);
h1 = h2 = t1 = t2 = 1;
flag = true;
solve();
if(flag == true)
{
for(i = t1 - 1;i >= h1;i --)
printf("%d ",que1[i]);
putchar(10);
}
else
puts("Impossible");
}
return 0;
}