시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 (추가 시간 없음) | 1024 MB | 62 | 18 | 17 | 30.357% |
A group of $n$ exchange students at Reykjavik University is lining up to get their group photo taken. From left to right, the heights of the students are $g_1, g_2, \ldots, g_n$. However, the photographer would like to rearrange the students such that the order of their heights becomes $h_1, h_2, \ldots, h_n$. In order to do this, the photographer will repeatedly exchange two exchange students. Two exchange students can only be exchanged if they can see each other, that is, if every student in between them has strictly smaller height than the two students to be exchanged.
Determine the minimum number of exchanges needed to arrange the students in the photographer's preferred order, and find a suitable sequence of exchanges of this minimal length. The photographer only has time for at most $2\cdot 10^5$ exchanges. If more are needed, you only need to determine the first $2\cdot 10^5$ exchanges.
The input consists of:
It is guaranteed that $(h_1, \ldots, h_n)$ is a permutation of $(g_1, \ldots, g_n)$.
First output an integer $s$, the minimum number of exchanges needed. Then print $\min(s, 2\cdot 10^5)$ exchanges, each consisting of two integers $i$ and $j$, the one-based positions of the students that must be exchanged in this step.
If there are multiple valid solutions, you may print any one of them.
3 2 1 3 3 1 2
1 1 3
5 6 7 5 9 6 9 6 7 6 5
4 3 4 4 5 1 2 1 3
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2021 E번