루미 알고리즘

#1338다이아Bokrecesioner

PO 2014 훈련 캠프코딩출제 Emanuel Gedin스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

En bokrecensent har läst N böcker som ska recenseras. Varje recension ska avslutas med att boken tilldelas ett betyg på en skala från 1 till M. Det kan vara svårt att direkt välja ett absolut betyg för varje bok, så bokrecensenten tycker att det är mycket enklare att jämföra två böcker i taget med varandra och beskriva vilken av dem som är bäst.

Bokrecensenten har numrerat böcker med heltal från 1 till N och vill nu bestämma deras betyg a_1, a_2, …, a_N. För att göra det har bokrecensenten gjort R jämförelser som beskriver relationen mellan a_i och a_j, för några böcker i, j.

Bokrecensenten är nöjd med vilken betygsättning som helst, så länge alla krav från jämförelserna är uppfyllda. Hjälp bokrecensenten att hitta en sådan betygsättning.

Indata

Första raden består av tre heltal, N (1 ≤ N ≤ 10^5), M (1 ≤ M ≤ 10^5), R (1 ≤ R ≤ 5 · 10^5), antalet böcker, högsta möjliga betyget och antalet jämförelser.

Sedan följer R rader med relationer som ska vara uppfyllda. Varje sådan rad har formatet "<i> <relation> <j>", som beskriver relationen mellan a_i och a_j. i och j är heltal mellan 1 och N, i ≠ j. Relationen r är någon av strängarna '<', '=', '<=', och detta beskriver just att a_i <relation> a_j måste gälla. Inget par av böcker kommer att jämföras mer än en gång.

Utdata

Skriv ut en lista med heltal a_1, a_2, …, a_N sådan att alla relationer håller, och alla tal är på intervallet [1, M]. Om det finns flera lösningar, skriv ut vilken som helst. Om det är omöjligt, skriv ut -1.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängvärdeGränser
130R kan bara vara <
230R kan bara vara < eller =
340Inga ytterligare begränsningar

Förklaring av exempelfall 1

I det första indataexemplet så är 1 2 1 3 3 en giltig lösning. Detta kan verifieras genom att se att alla tal ligger på intervallet [1, 3], och att talen uppfyller de fyra relationerna a_1 < a_2, a_2 < a_4, a_3 < a_2 och a_2 < a_5.

예제

예제 1

입력
5 3 4
1 < 2
2 < 4
3 < 2
2 < 5
출력
1 2 1 3 3

예제 2

입력
3 10 3
1 < 2
2 < 3
3 < 1
출력
-1

예제 3

입력
6 4 6
2 < 1
3 = 1
6 = 3
6 < 5
5 < 4
1 < 4
출력
2 1 2 4 3 2

예제 4

입력
7 3 8
1 <= 2
5 = 7
2 <= 7
6 < 1
5 <= 1
2 < 3
6 <= 4
4 = 3
출력
2 2 3 3 2 1 2

출처 표기

출처: Programmeringsolympiaden 2014년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.