Kolejka

04.06.2010
Trudność

Kolejka

Limit czasowy: 1000 milisekund
Limit pamięciowy: 36320 kilobajtów


Budowniczy Adrian zatrudniony przy budowie nowego centrum handlowego nie ma dzisiaj zbyt wiele pracy. Dzięki temu może oddać się zbieraniu materiałów do jego pracy naukowej poświęconej kolejkom sklepowym.

Adrian obserwuje kolejkę do pobliskiego sklepu i zapisuje jakie miejsce w kolejce zajęła każda z kolejno przychodzących osób. Na początku dnia nikt nie stał w kolejce. Kolejne osoby niekoniecznie stawały na końcu. Mogli umówić się z kimś, zapłacić komuś, dać komuś coś, lub załatwić to w jeszcze inny sposób i wejść w dowolne miejsce w kolejce. Każda osoba, która raz stanęła w kolejce, nie wyszła z niej aż do południa, kiedy okazało się, że sklep nie zostanie dzisiaj otwarty i wszyscy się rozeszli.

Adrian zastanawia się, czy używając jego notatek można odtworzyć ustawienie kolejki tuż przed rozejściem się ludzi.

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ). Następnie opisywane są kolejne zestawy testowe.

W pierwszej linii opisu zestawu znajduje się liczba naturalna N ( 1 <= N <= 100 000 ) oznaczająca liczbę ludzi, którzy od rana do południa stanęli w kolejce. W drugiej linii znajduje się N liczb  Xi ( 0 <= Xi < i, dla 1 <= i <= N ). Jeśli Xi jest równe 0, oznacza to, że i-ta osoba stanęła na samym początku kolejki, w przeciwnym wypadku i-ta osoba stanęła za osobą, która w chwili jej przyjścia była Xi-tą osobą licząc od początku kolejki.

Wyjście

Dla każdego zestawu należy w osobnej linii wypisać ciąg N liczb oddzielonych pojedynczymi spacjami. i-ta liczba powinna być ostateczną pozycją w kolejce osoby, która dołączyła do niej jako i-ta. Jeśli osoba stoi na początku kolejki, jej pozycja to 1, pozycja za nią 2, itd.

Przykład

Wejście Wyjście
2
5
0 0 0 0 0
5
0 1 2 3 4
5 4 3 2 1
1 2 3 4 5
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com