Runda 19 [Hard] - Robaki reaktywacja

02.05.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

runda 19; kategoria Hard

Limit czasowy: 1s; Limit pamięciowy: 32MB


Robaki reaktywacja

Czy pamiętacie zadanie Robaki z Zawodów Stałych? Tym razem stoimy przed trudniejszym zadaniem!

Na pręcie długości $ L $ umieszczono w pewnych miejscach wiele robaczków. Każdy z nich ma określony kierunek poruszania się - w kierunku lewego końca pręta, lub w kierunku prawego końca pręta. Każdy porusza się z tą samą stałą prędkością.

Robaczki są całkiem masywne (choć rozmiarem równe punktowi!) i gdy dwa spotkają się na pręcie idąc w przeciwne strony, oba w mgnieniu oka zmieniają kierunki - tak, jakby odbiły się od siebie. Jeśli jakiś robak dotrze do lewego lub prawego końca pręta, spada zeń i nie ma już po nim śladu. 

Zadanie, jakie nasuwa się szybko - znająć początkowe położenia robaczków na pręcie i kierunki, w których zmierzają, odpowiedz, który z nich spadnie z pręta jako ostatni? Możesz założyć, że dane będą dobrane w ten sposób, że nie dojdzie do sytuacji, w której kilka robaków spadałoby w ostatniej chwili.

Wejście:

Pierwsza linia wejścia zawiera dwie liczby - $ n $ oraz $ L $ - odpowiednio liczbę robaków oraz długość pręta ($ 1 \leq n \leq 10^{5} $, $ 1 \leq L \leq 10^{9} $). W kolejnych $ n $ liniach znajdują się pary liczb cakowitych  $ p_{i} $ $ k_{i} $ - odpowiednio położenie i kierunek robaczka. Pręt traktujemy jak odcinek $ [0,L] $. Wartość $ p_{i} $ oznacza punkt na tym odcinku na którym znajduje się robaczek, za to $ k_{i} $ wyznacza kierunek - $ k_{i}=0 $ mówi, że robaczek zmierza w kierunku punktu $ 0 $, $ k_{i} = 1 $, że w kierunku punktu $ L $. ($ 0 \leq p_{i} \leq L $, $ k_{i} \in \left\{0,1\right\} $). 

Wyjście:

Wyjście powinno zawierać jedną liczbę - numer robaka, który spadnie z pręta jako ostatni. Robaki numerowane są od $ 1 $ do $ n $ zgodnie z kolejnością na wejściu.

Przykład:

Wejście:

4 10
1 1
5 0
7 0
8 1

Wyjście:

3

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com