Foreign Trip
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
More and more countries are reopening their borders after the burdock-virus pandemic. Marichka and Zenyk decided to go on a trip with their friends. For this, they all need to get vaccinated.
Friends went to the clinic, stood in a giant queue, and bought a large box of vaccines — \(x\) doses of the first type and \(y\) doses of the second type. Now, each of the \(n\) participants of the trip needs to decide which type of vaccine they will be inoculated with. It is known that the benefit of vaccinating the \(i\)-th participant of the group with the first type of vaccine is \(a_i\), and with the second type of vaccine — \(b_i\).
The friends want to distribute the vaccines among the participants so that each participant receives exactly one dose of vaccine and the total benefit is maximized. Will you help them?
Input
The first line contains three integers \(n\), \(x\), and \(y\) — the number of trip participants, the number of doses of the first type, and the number of doses of the second type.
Each of the next \(n\) lines contains two integers \(a_i\) and \(b_i\) — the benefit of vaccinating the corresponding participant with each of the vaccine types.
Output
Print a single line of \(n\)
characters. The \(i\)-th character
should be A if the \(i\)-th participant should take the first
type of vaccine, and B for the second. If there are several
ways to achieve the maximum benefit, print any of them.
Constraints
\(1 \le n \le 10^5\),
\(0 \le x, y \le 2 \cdot 10^5\),
\(x+y \ge n\),
\(0 \le a_i, b_i \le 10^9\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 2 2 1 3 7 4 9 2 3 3 | BAAB |
Notes
The total benefit will be 22. A larger value cannot be achieved.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
Foreign Trip - Editorial
Suppose we have an unlimited supply of the first vaccine but only one dose of the second. If everyone gets the first vaccine, the total benefit is \(A_1 + A_2 + ... + A_n\). If the \(i\)-th person gets the second vaccine instead of the first, the benefit changes by \(B_i - A_i\). So it only makes sense to give the second vaccine to the participant with the largest \(B_i - A_i\), and only if \(B_i - A_i\) is positive for them.
Similarly, if we have only two doses of the second vaccine, it may only make sense to give them to the two participants with the largest values of \(B_i - A_i\).
Generalizing this reasoning, we get the full solution. Sort all participants in non-increasing order of \(B_i - A_i\). The second vaccine goes to some group of people at the beginning of this sorted list. We only need to decide how many people at the beginning of the list should get the second vaccine. Ideally, we would give the second vaccine to everyone with positive \(B_i - A_i\) and the first vaccine to the rest. But then we might run out of one of the vaccines. So we must also take into account that the second vaccine must go to at least \(n - x\) and at most \(y\) participants.
Complexity: \(O(n \log(n))\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|