Editorial for IOI '09 P5 - Garage

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The problem is essentially a straightforward simulation, but the data structures required are not completely trivial. A simple implementation that does not require any kind of data structure beyond a fixed-size array will keep track of:

  • for each car, its state (absent, in the queue, or parked), its parking space (if parked), and its arrival time (if in the queue);
  • for each parking space, whether there is a car parked there.

Now one can process the input events one at a time. When a car arrives, loop over all parking spaces to find the first empty one. If one is found, park the car there. Otherwise, the car will have to go into the queue — so record its arrival time.

When a car leaves the garage, it will be replaced by the car at the front of the queue (if any). Loop over all cars to find the car that arrived earliest and is still in the queue. If one is found, park it in the parking space that has just been freed up, and mark it as no longer in the queue.

This solution runs in \mathcal O(M^2+MN) time. This can be improved: keeping the queue in a separate array reduces this to \mathcal O(MN), and also keeping the available parking spaces in a binary heap reduces it to \mathcal O(M \log N). However, these optimizations are not necessary to receive a full score.


There are no comments at the moment.