KOILINE - Line up
N people are lined up in a straight line to enter a concert. Each person in this line knows how many people in front have shorter or same heights. Let's call the sequence representing these numbers S. So in other words, S[i] means that there are S[i] people in front of the ith person who have shorter or same heights than that of person i.
Given the heights of N people and a sequence S, determine the correct order of people lined up. (left is front)
Input
The first line of the input is an integer N. (1<=N<=100,000)
The next N lines each consists of one integer H. (1<=H<=2*10^9) These N integers are the heights of people lined up.
Then, sequence S is given in a single line, separated by a space.
Output
Determine the correct ordering of people lined up. Total of N lines should be output. The integer on the ith line represents the height of the ith person in the line.
Example
Input: 12
120
167
163
172
145
134
182
155
167
120
119
156
0 1 0 0 3 2 6 7 4 6 9 4
Output: 134
167
120
119
156
120
167
182
155
163
172
145
hide comments
Rafail Loizou:
2020-09-11 11:31:33
forgetting to return the answer cost me a lot of submissions XD... always remember to return your binary searches result in any case XD |
|
smso:
2018-07-30 12:57:20
hint: look from the back of sequence S, use segment tree to get over TLE |
|
Utkarsh Agarwal:
2015-05-26 02:19:46
accepted !! :) changed two arrays of length 10^5 from long int to int, but the time it took to run increased instead :P same algo. same code :P Last edit: 2015-05-26 02:27:23 |
|
Rishav Goyal:
2014-04-30 14:51:51
woe !! heights do fit in int!! moreover more implementation !! huh!! finally AC!! |
|
Dario Sindicic:
2014-03-01 13:07:16
O( N*lgN*lgN) pass |
|
:D:
2012-05-22 13:44:28
heights DO fit in int. I was reading them into that format in my ACC submission. |
|
charvi:
2011-09-30 06:32:54
I have done KOILINE but for the same code I am getting TLE for SSEQ and orders |
|
Santiago Palacio:
2011-06-13 21:26:54
@Ashish Massand: 2*10^9 < 2^63, so they do fit. |
|
Ashish Massand:
2011-06-13 08:11:09
The heights don't fit in int they fit in long long int even though in the specification it is said h <= 2*10^9
|
Added by: | Lawl |
Date: | 2011-06-02 |
Time limit: | 0.703s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | 2011 KOI Regional |