Stock Prices#2753
Buy low, sell high. That is the main principle for making a profit in the stock market (we will ignore short selling here). Of course, nobody can predict the future price of a stock, so it is difficult to determine exactly when to buy and sell, and how much profit can be made by buying and selling a stock repeatedly.
However, if you have the price history of a stock for the last days, it is possible to determine the maximum achievable profit. In this problem, instead, we are interested in finding the k_1 lowest and k_2 highest prices in that history.
The input consists of multiple cases. Each case starts with a line containing the positive integers , k_1, and k_2 (n \leq 1000000, k_1 + k_2 \leq n, k_1, k_2 \leq 100). The next line contains integers giving the stock prices over the last days: the -th integer (1 \leq i \leq n) gives the stock price on day . All prices are non-negative. The input is terminated by a line containing n = k_1 = k_2 = 0; this case should not be processed.
For each case, output three lines. The first line contains the case number (starting from ). The second line contains the days on which the k_1 lowest stock prices occur, listed in ascending order. The third line contains the days on which the k_2 highest stock prices occur, listed in descending order. Entries in each list should be separated by a single space. If there are multiple correct lists for the lowest prices, choose the lexicographically smallest list. If there are multiple correct lists for the highest prices, choose the lexicographically largest list.
Example 1