All submissions for this problem are available.
Sutrave is a great Chef and runs his own bakery. He likes to decorate his cakes very well to impress his customers. Therefore, he ends up taking a lot of time and is able to bake only 10 cakes in an hour. As he is very famous, many customers come to him everyday and that keeps him very busy. However, Sutrave believes that the people who are more regular help him make higher profit and hence, he bakes cakes for the more regular customers before he bakes the other cakes. In case he finds that two customers are equally regular, he bakes for the customer who came earlier.
Each customer has a customer ID C(1<=C<=100,000), regularity factor R(1<=R<=100) [R=100 is more regular than R=1] and visits the store at the Kth hour(1<=K<=100). Customer ID is unique for every customer. Each customer comes only once and orders only one cake.
Note: Thought the customers do not visit after the 100th hour, Sutrave might take more than 100 hours to bake the cakes. Also, any number of customers can visit in any given hour
First line contains number of test cases T(1<=T<=100)
In each test case the first line contains the total number of customers N(1<=N<=100,000) that visit. Next N lines contain the customer ID C, regularity factor R and the hour K for the N customers. This inputs are in the order in which the customers visit the bakery.
Output contains T parts.
In each test case, for every line, the first number indicates the hour and the proceeding numbers in the same line indicate the Customer IDs of the customers, whose cakes have been made in that hour. This hourly list of Customer IDs varies as: Customer ID of a more regular customer appears to the left of a less regular customer.
Input: 2 3 34 50 1 65 20 3 99 75 3 15 11 26 1 77 56 1 43 85 1 12 92 1 17 20 1 72 40 1 69 55 1 82 99 1 67 38 1 63 67 1 99 12 1 92 50 1 40 50 1 24 70 2 33 30 2 Output: 1 34 3 99 65 1 82 12 43 63 77 69 92 40 72 67 2 24 33 11 17 99
The above input has 2 test cases. In the first case, there are 3 customers whose customer IDs, regularity factors and hours of visit are given. Only one customer arrives in the first hour hence, Sutrave bakes his cake in the hour. No customer arrives in the second hour hence Sutrave does not bake any cake in the second hour. Next 2 customers arrive in the third hour and Sutrave bakes their cakes in the third hour based on their regularity factor.
In the second test case, there are 15 customers out of which 13 arrive in the first hour. Hence, Sutrave bakes for the top 10 most regular and the remaining 3 cakes are shifted to be baked in the next hour. However, 2 more customers arrive in the 2nd hour. Hence, out of these total of 5 cakes, Sutrave bakes them based on the regularity factor.
Output is the corresponding customer IDs in order of which their cakes were baked.
|Time Limit:||0.124661 - 1.01 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.