Baltic Olympiad in Informatics 2018 Open - day 2

Start

2018-04-29 09:30 CEST

Baltic Olympiad in Informatics 2018 Open - day 2

End

2018-04-29 14:30 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -570 days 14:53:52

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
Prąd przemienny

Ferdynand bawi się w domu swoją zrobioną na zamówienie kolejką, która napełnia go wielką dumą. Tor kolejki podzielony jest na $N$ segmentów połączonych w kółko, ponumerowanych $1, 2, \dots , N$ w kolejności zgodnej ze wskazówkami zegara. Segmenty są zasilane prądem za pomocą $M$ przewodów poprowadzonych wzdłuż toru. Wzdłuż każdego segmentu biegnie co najmniej jeden przewód.

Ferdynanda zaczął nudzić pociąg, który nie robi nic więcej poza jeżdżeniem w kółko, więc postanowił do każdego segmentu dodać przełącznik zmieniający kierunek jazdy, aby móc aranżować wypadki i inne nieco bardziej ekscytujące scenariusze. Jednak takie przełączniki też wymagają prądu. I to nie byle jakiego – musi to być prąd przemienny. 1

Ferdynand wymyślił, że doskonałą metodą uzyskania prądu przemiennego będzie podłączenie przełącznika do dwóch źródeł prądu płynącego w przeciwnych kierunkach. Każdy przewód przewodzi prąd wyłącznie w jedną stronę (zgodnie lub przeciwnie do wskazówek zegara), lecz Ferdynand może wybrać w którą. Postanowił więc tak podobierać kierunki prądu w poszczególnych przewodach, aby wzdłuż każdego segmentu biegł przewód przewodzący prąd zgodnie ze wskazówkami zegara oraz przewód przewodzący w przeciwnym kierunku.

Potrafisz pomóc mu w tym zadaniu?

\includegraphics[width=0.5\textwidth ]{alternatingfig.pdf}

Rozwiązanie pierwszego testu przykładowego. Strzałki na zewnątrz toru przedstawiają przewody. Kierunek i kolor strzałek oznacza kierunek, w którym dany przewód przewodzi prąd. Odwracając kierunki wszystkich strzałek również uzyskamy poprawne rozwiązanie: 11010.


Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $N$ i $M$ oznaczające odpowiednio liczbę segmentów toru i liczbę przewodów. Każdy z następnych $M$ wierszy zawiera dwie liczby całkowite $1 \le a, b \le N$ oznaczające przewód biegnący przez segmenty $a, a+1, \dots , b$. Jeśli $b$ jest mniejsze niż $a$ oznacza to, że przewód biegnie przez segmenty $a, \dots , N, 1, \dots , b$. W przypadku $a=b$ przewód pokrywa tylko jeden segment.

Wyjście

Na wyjście wypisz pojedynczy wiersz zawierający $M$ znaków 0 lub 1. $i$-ty znak oznacza kierunek prądu płynącego przez $i$-ty przewód z wejścia – $0$ oznacza kierunek zgodny ze wskazówkami zegara, $1$ przeciwny. W przypadku wielu możliwych rozwiązań wypisz dowolne z nich.

Jeśli nie da się tak pokierować prądu w przewodach, aby przez każdy segment biegł prąd w obu kierunkach, wypisz ,,impossible”.

Ograniczenia

Zestaw testów dzieli się na kilka grup, każda jest warta pewną liczbę punktów. Każda grupa składa się z jednego bądź większej liczby testów. Aby otrzymać punkty za daną grupę, Twoje rozwiązanie musi przejść wszystkie testy z tej grupy. Ostateczny wynik za zadanie jest liczony jako maksymalny wynik z pojedynczych zgłoszeń.

Grupa

Punkty

Limity

Dodatkowe ograniczenia

1

13

$2 \le N, M \le 15$

 

2

20

$2 \le N, M \le 100$

 

3

22

$2 \le N, M \le 1000$

 

4

19

$2 \le N, M \le 100\, 000$

Dla żadnego przewodu nie zachodzi $b < a$.

5

26

$2 \le N, M \le 100\, 000$

 
Przykładowe wejście 1 Przykładowe wyjście 1
10 5
1 5
6 7
5 1
7 2
2 4
00101
Przykładowe wejście 2 Przykładowe wyjście 2
10 5
1 4
2 5
4 7
6 10
8 1
impossible
Przykładowe wejście 3 Przykładowe wyjście 3
5 2
1 5
3 3
impossible
Przykładowe wejście 4 Przykładowe wyjście 4
5 3
3 3
2 1
4 2
101

Footnotes

  1. Taka konstrukcja naprawdę działa w szwedzkich kolejach – wszystkie przełączniki (,,växlar”) używają prądu przemiennego (,,växelström”).