Elevator Operation
Time limit1sMemory limit512 MB
Each floor holds one person with a known destination; drive a one-person elevator from floor 1 so everyone reaches their target floor using the fewest button presses, and output one optimal button order.
- Level
Hard8 of 10
- Topics
- Graph, Greedy, Implementation, Simulation
- Solved
- No attempts yet
Problem
Uichan manages the headquarters building of "Aju Software". One day, while he was going through his usual dull routine, the elevator at the Aju Software headquarters broke down. When he told the employees that the elevator would take a day to repair, they started to complain. Uichan had no choice but to use the emergency elevator, which can only be operated from the control room.
The emergency elevator holds at most one person, and it can only be operated from the control room. The control room has buttons that move the elevator, and pressing the button for a floor moves the elevator to that floor.
Uichan has watched the employees' movement patterns on the control room CCTV every day for so long that he is sick of them, so just by seeing who is waiting in front of the elevator on the CCTV he can tell which floor that person wants to go to. Uichan checks who is waiting on the CCTV, then moves the elevator with as few operations as possible to drop each person off at the floor they want.
On each floor, exactly one person is waiting. Output the minimum number of button presses needed to drop everyone off at the floor they want, and the order of the buttons to press. The elevator starts on floor 1.
Input
The first line gives the number of floors in the building, N. (2 ≤ N ≤ 100,000)
The next line gives N integers A1, ..., AN, where Ai is the floor the person waiting on floor i wants to go to. (1 ≤ Ai ≤ N, 1 ≤ i ≤ N)
No person wants to go to their current floor. (Ai ≠ i)
Output
The first line gives the minimum number of button presses.
The next line gives the order of the buttons to press, separated by spaces. If there are several valid ways, output any one of them.
Hint
For example 1, pick up the person on floor 1, move to floor 4 and drop them off, pick up the person on floor 4, move to floor 5 and drop them off, pick up the person on floor 5, move to floor 2 and drop them off, pick up the person on floor 2, move to floor 4 and drop them off, move to floor 3, then pick up the person on floor 3, move to floor 1 and drop them off.