Description
Today it's May 4th, so let's celebrate Star Wars Day by building a taxi service for the rebels!
The system needs to have the following commands:
- addRider <rider_id> <rider_val>
- Add a new rider to the system with ids <rider_id> and <rider_val>, which are values computed by AI to represent their classified information.
- addDriver <driver_id> <driver_val>
- Add a new driver to the system with ids <driver_id> and <driver_val>, which are values computed by AI to represent their classified information.
- match
- Match a driver with a rider following these rules:
- Match the driver with the highest <driver_val> and rider with the highest <rider_val>
- If there are 2 drivers/riders with the same <driver_val>/<rider_val>, the one who is added earlier to the system has higher priority.
- Output (<driver_id>, <rider_id>) and remove both driver and rider from the system.
Note
- If there are only no driver or no rider available for matching, output (-1, -1).
- You need to select the suitable tree structure and representation method for the request.
- Only <iostream>, <string>, <vector> are allowed for this question.
Input
First line contains an integer N denoting the number of input commands.
Every one of the N lines will be one of the three commands.
1<= # of drivers/riders used in process <= 500000
1 <= <rider_id>, <rider_val>, <driver_id>, <driver_val> <= 500000
All <driver_id>/<rider_id> are unique.
For testcases 1-5, all <driver_val>/<rider_val> are unique
For testcases 5/7/8, N>=100000, you need to implement an efficient solution for passing them.
Output
For every match command, output (<driver_id>, <rider_id>) with a newline character.
You don't need to output anything for other commands.
Remember to output (-1, -1) if there are no driver/rider available to match.
Tags