Interactive Permutation Guessing

시간 제한1초메모리 제한128 MB

요약
숨겨진 크기 n 순열을 알아내야 한다. 임의의 순열을 질의하면 최장 공통 부분순열의 길이를 돌려받으며, 질의는 5n제곱 회로 제한된다.
난이도

어려움10점 중 8점

유형
완전 탐색, 그리디, 조합론, 구현
정답자
아직 제출이 없습니다

문제

There is a permutation a of size n that you have to guess interactively.

You are allowed to make queries of the following kind. You output any permutation b of size n. The information given back to you is the length of the longest common subsequence of permutations a and b.

입력

The first line of the standard input contains integer n, the size of the permutation (1 ≤ n ≤ 40).

Each of the next lines of the standard input contains response to your query — the length of the longest common subsequence of the permutation queried by you and the permutation a.

출력

Each line of the standard output should contain a space-separated list of integers that form a permutation you’re querying.

Your can make at most 5n2 queries.

You must flush the standard output after printing each line. You must not print any lines after you receive the response n, just exit.

예제1

  1. 예제 1

    입력
    4
3
2
2
4
    예상 출력
    1 2 3 4
1 3 4 2
4 1 2 3
3 1 2 4