Around the Table

시간 제한6초메모리 제한2048 MB

요약
최대 60번의 착석 실험을 통해 각 사람이 둘러앉은 자리에서 양옆 사람보다 일찍 도착한 사람 목록을 받고, 비밀 좌석 배치를 알아낸다.
난이도

어려움10점 중 9점

유형
조합론, 분할 정복, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

There will be nn people numbered from 11 to nn, and a room with a round table that has exactly nn seats, with each person having a distinct reserved seat that hasn't been revealed yet.

To figure out the reserved seat of each person, up to 6060 meetings of the nn guests can be organized in the dining room. Before each meeting, you can decide the order in which the guests will arrive. After each meeting, you will receive a list of the guests who arrived earlier than both of their neighbors in the secret seating arrangement at the table.

For each seat, find the person it is reserved for using the information gathered by the result of the meetings.

예제1

  1. 예제 1

    입력
    6

2 1 2

2 5 6

2 3 5

2 3 2
    예상 출력
    
? 1 2 3 4 5 6

? 6 5 4 3 2 1

? 3 4 5 1 6 2

? 3 1 2 4 5 6

! 3 4 6 2 5 1