Pongos P52016


pdf   zip


Each Christmas holidays, n friends meet to celebrate a tradition. There are n useless presents, which are called pongos. The pongos are wrapped up with newspaper, so at the beginning of the game the only available information for each pongo ‍i is ai: how cool i seems while it is wrapped up. Let ri be the real coolness of i. This real coolness is only known when the pongo is unwrapped. The higher the value of ai, the cooler the pongo looks when wrapped. The higher ri, the cooler it is when unwrapped.

The game goes as follows. The participants are numbered from 0 to n−1. At the beginning of the j-th round (from 0 to n−1), each of the first j participants has an unwrapped pongo at his hands, which is seen by everybody. The round starts with the participant number j. He always takes the pongo that looks or is coolest according to the available information: if the pongo is still unchosen and therefore wrapped up, he uses ai, and if the pongo is already on some participant’s hands, he uses ri.

If a participant takes a wrapped pongo, he unwraps it and the game goes to the next round. If he takes a pongo from another participant, the participant that just lost his pongo takes the pongo that is or looks coolest among those that have not been chosen in the current round. The round continues like this until someone takes a wrapped pongo and unwraps it.

This game is deterministic. Can you tell the real coolness of the pongo that every person has at the end of the game?


Input consists of several cases. Every case starts with n, followed by the n integers ai, followed by the n integers ri. You can assume 1 ≤ n ≤ 104. All the values for ai and ri are distinct integers between 0 and 2n−1.


For every case, print the n integers rj, where rj is the real coolness of the pongo at the hands of the j-th person at the end of the game.

Public test cases
  • Input

    1 0 2
    5 4 3
    3 9 7 1 2 11
    10 4 6 5 8 0
    0 1 2 3 4
    9 8 7 6 5


    3 4 5
    0 4 6 5 8 10
    7 5 9 6 8
  • Information
    Cesc Folch Aldehuelo
    Official solutions
    User solutions