Lost Cows

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 11583 Accepted: 7444

Description

N (2 <= N <= 8,000) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

Input

* Line 1: A single integer, N

* Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

Output

* Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

Sample Input

5

1

2

1

0

Sample Output

2

4

5

3

1

分析:

题目大意:

就是有一帮头不行的序列，从第二个数开始就知道前面比他编号小的数量。之后要求你复原整个序列。

所以！线段树！

不，线段树写起来麻烦。

树状数组。

用树状数组来存比这个小的数还有几个/之后我们从给出的序列从后往前找。

从后往前找是因为，序列表示的是与前面的编号小的关系。一旦后面的确立了，这个树状数组，就是关于所有前面的数，没有找过的。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include<cstdio> #include<algorithm> using namespace std; int n; int s[9000]; int tree[10000]; int ans[9000]; int lowbit(int x) { return x&-x; } int sum(int x) { int sum=0; while(x>=1) { sum+=tree[x]; x-=lowbit(x); } return sum; } int find_tree(int x) { int l=1,r=n; while(l<r) { int mid=(l+r)>>1; if(sum(mid)<x) { l=mid+1; } else { r=mid; } } return l; } int change(int x) { while(x<=n) { tree[x]-=1; x+=lowbit(x); } return 0; } int main() { scanf("%d",&n); for(int i=2;i<=n;++i) { scanf("%d",&s[i]); } for(int i=1;i<=n;++i) { tree[i]=lowbit(i); } for(int i=n;i>=1;--i) { int x=find_tree(s[i]+1); ans[i]=x; change(x); } for(int i=1;i<=n;++i) { printf("%d\n",ans[i]); } return 0; } |