Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution E - Bigger Picture
E. Bigger Picture
Score: 1
CPU: 3s
Memory: 1200MB
CPU: 3s
Memory: 1200MB
In our country, sometimes organizers organize competition keeping a “big picture” in mind. They don’t care about the fairness of a competition. They just see that “lots of people got aware.” And that’s a great achievement for them while a good participant’s morale may get hurt by the unfairness but that gives the least amount of headache to the organizers. So, let’s organize a competition ourselves with a bigger picture in mind. There are n rooms in the competition arena. We are given the number of participants in each room. If we are to choose the first, we will look for the room with the maximum number of participants, in the case of more than one such room, we choose the room with the minimum id among the ones with maximum number of participants. After choosing the room, we randomly remove one participant from that room. Then we proceed on in the similar fashion until we rank all the participants. For example, suppose there are 3 rooms with 2, 1 and 3 participants respectively:
Number of participants | Selected room (1 based) |
2, 1, 3 | 3 (first came from 3rd room) |
2, 1, 2 | 1 (second from 1st room) |
1, 1, 2 | 3 (third from 3rd room) |
1, 1, 1 | 1 (forth from 1st room) |
0, 1, 1 | 2 (fifth from 2nd room) |
0, 0, 1 | 3 (sixth from 3rd room) |
0, 0, 0 | No participants are left |
Given n and the number of participants in each of these n rooms. For the given K, find the room from where the K’th participant will be chosen from.
Input
First line of the input will be T (≤ 20), number of test cases. Hence T cases will follow.
First line of the test case will contain two numbers: n and m (1 ≤ n ≤ 100,000, 1 ≤ m ≤ 1000). Second line will contain n non-negative numbers, each not exceeding 1,000,000,000,000. The i’th of these numbers denote number of participants in the i’th room. Third line will contain m numbers, each denoting a K (1 ≤ K ≤ total number of participants). The K’s in a test case would be distinct.
Output
For each test case first print the case number, followed by m answers to the given queries. For details of the output format please check the sample input/output.
Sample
Input | Output |
---|---|
3 3 6 2 1 3 4 3 1 6 2 5 5 3 2 5 2 5 1 7 8 9 5 1 1 2 3 4 5 1 | Case 1: 1 3 3 3 1 2 Case 2: 1 2 3 Case 3: 5 |
*Warning: Large I/O file, user faster input output functions.
Comments
Post a Comment