Lost Cows
| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 2824 |
|
Accepted: 1742 |
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
Source
Analysis
Which number can we determine at the first glance of the input data? Of course, the answer is the tail. Suppose the last number of the input data, which is the number of cows with lower brand number than it, is a[n]. According to the defination, the last cow gets the (a[n]+1)th number, since there are a[n] brand number before. What's more, the brand number is constrained in range from 1 to n, so the last number is well ensured.
Later, the earlier one will be determined in a set containing the numbers range from 1 to n except b[n], which is the brand number of the last cow. Obviously, the brand number is the (a[n-1]+1)th number in the set. The problem turns to be the method to save and search used numbers. If we create a constantly array, the cost of time in deleting and searching is both O(n) and the whole cost is o(n^2). Just consider about the segment tree. Create a segment tree of range [1,n], and the number of tree[p] is the number of brands used. When a number is inserting, calculate the remaining number of the left range: m-l+1-tree[p]. If it is larger than the current number, which is a[i]+1, then searching the left child. Otherwise, search the right one. When it is searching, adding the current root since it is clear to see that a new member is coming now. At last, when the search comes to an end and find a leave, record the range number.
My code:
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX 8000
int main()
{
int n,i;
int a[MAX],b[MAX];
int tree[4*MAX+1];
scanf("%d",&n);
a[0]=0;
for (i=1;i<n;i++)
scanf("%d",a+i);
for (i=n-1;i>=0;i--){
int l,r,p,m,no;
no=a[i]+1;
l=1;r=n;p=1;
while (l<r){
tree[p]++;
m=(l+r)>>1;
if (m-l+1-tree[2*p]>=no ){
r=m;
p<<=1;
}
else {
no-=m-l+1-tree[2*p];
l=m+1;
p=2*p+1;
}
}
tree[p]++;
b[i]=l;
}
for (i=0;i<n;i++)
printf("%d\n",b[i]);
return 0;
}