P5262 [ROI2007 / JSOI2013] PE Class

There are $N$ students in the PE class, with student IDs from $1$ to $N$. JYY’s PE teacher KFC has a special way to arrange the line: - KFC first makes the $N$ students stand in a row from left to right in increasing order of student ID. Then, starting from the far left of the line (in front of the first student), KFC walks to the right until reaching the $(N-1)$-th student. - Next, KFC returns to the first student and starts walking to the right again. In total, KFC walks $N-1$ times. - Each time when KFC reaches the $i$-th student, KFC compares the heights of the $i$-th and $(i+1)$-th students. If the student on the left (the $i$-th) is taller than the student on the right (the $(i+1)$-th), KFC swaps their positions in the line. After all $N-1$ walks are finished, KFC will choose some students on the far right of the line to move desks. Naturally, JYY wants to stand as far to the left as possible to increase his chances to play soccer. In addition, JYY has a special trick: when KFC is about to walk up to him, JYY can squat down to tie his shoelaces. If JYY squats down to tie his shoelaces, then during that walk, the easygoing teacher KFC will not make JYY compare heights with adjacent students, and of course will not make JYY swap positions with adjacent students (only JYY is smart enough to squat down; all other students will honestly let KFC compare heights). Squatting down to tie shoelaces costs a lot of energy. To save energy for playing soccer, JYY can squat at most $K$ times. JYY wants to know what squatting strategy can make him stand as far to the left as possible in the line. Use a string of length $N-1$ to represent a strategy: if the $i$-th character of the string is `+`, it means JYY squats down to tie his shoelaces during the $i$-th walk; if it is `-`, it means JYY will honestly compare heights.

The first line contains three integers $N, P, K$, representing the number of students, JYY’s student ID, and the maximum number of times JYY can squat. The second line contains $N$ integers, where the $i$-th integer is $h_i$, the height of the student with ID $i$.

The first line contains one positive integer, the leftmost position JYY can reach under the best strategy. The second line contains a string of length $N-1$, representing the best strategy. If there are multiple best strategies, JYY wants the lexicographically largest one.

Constraints: $1\le P\le N\le 10^5$, $0\le K\le N-1$, $1\le h_i\le 10^9$. Translated by ChatGPT 5