|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||1024 MB||84||19||15||21.429%|
The city of Tehran is home to the National Library of Iran. The main treasure of this library is located in a long hall with a row of $n$ tables, labeled $0$ through $n-1$ from left to right. On each table there is one ancient handwritten book being displayed. These books are ordered based on their ages, which makes it hard for the visitors to search for books by title. So, the library manager has decided to sort the books in alphabetical order of their titles.
Aryan, a librarian, is going to do the job. He has created a list $p$ of length $n$, containing different integers from $0$ to $n-1$. This list describes the changes needed to rearrange the books into alphabetical order: for all $0 \leq i < n$, the book that is currently on table $i$ should be moved to table $p[i]$.
Aryan starts sorting the books at table $s$. He wants to return to the same table after finishing the job. Since the books are very valuable, he cannot carry more than one book at any time. While sorting the books Aryan will perform a sequence of actions. Each of those actions has to be one of the following:
For all $0 \leq i, j \leq n - 1$, the distance between tables $i$ and $j$ is precisely $|j-i|$ meters. Your task is to compute the minimum total distance Aryan needs to walk in order to sort all the books.
You should implement the following procedure:
int64 minimum_walk(int p, int s)
minimum_walk([0, 2, 3, 1], 0)
In this example, $n=4$ and Aryan is at table $0$ at the beginning. He sorts the books as follows:
Note that book on table $0$ is already in the correct place, table $0$, so Aryan does not have to pick it up. The total distance he walks in this solution is $6$ meters. This is the optimal solution; hence, the procedure should return $6$.
$n \le 4$ and $s = 0$
$n \le 1000$ and $s = 0$
$s = 0$
$n \le 1000$
no additional constraints
The sample grader reads the input in the following format:
The sample grader prints a single line containing the return value of
Olympiad > International Olympiad in Informatics > IOI 2017 > Day 2 6번
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)