P5200 [USACO19JAN] Sleepy Cow Sorting G

USACO January 2019 contest, Gold Group, Problem 2.

Farmer John is trying to line up his $N$ cows ($1\le N\le 10^5$), numbered $1\ldots N$ for convenience, before they head to the pasture for breakfast. Currently, the cows are standing in a line in the order $p_1,p_2,p_3,\ldots,p_N$, and Farmer John is standing in front of cow $p_1$. He wants to rearrange the cows so that their order becomes $1,2,3,\ldots,N$, with cow $1$ next to Farmer John. Today the cows are a bit sleepy, so at any time, only the cow directly facing Farmer John will pay attention to his commands. In one operation, he can command this cow to move back along the line by $k$ steps, where $k$ can be any number from $1$ to $N-1$. The $k$ cows she passes will move forward to make space, allowing her to be inserted right behind those $k$ cows in the line. For example, suppose $N=4$, and the cows start in the following order: ```plain FJ: 4 3 2 1 ``` The only cow paying attention to FJ is cow $4$. After he commands her to move back $2$ steps, the line becomes: ```plain FJ: 3 2 4 1 ``` Now the only cow paying attention to FJ is cow $3$, so in the second operation he can give a command to cow $3$, and so on, until the cows are sorted. Farmer John is eager to finish sorting so he can go back to his farmhouse and enjoy his own breakfast. Please help him find a sequence of operations that sorts the cows using the minimum number of operations.

The first line contains $N$. The second line contains $N$ space-separated integers: $p_1,p_2,p_3,\ldots,p_N$, describing the cows' initial order.

The first line contains an integer $K$, the minimum number of operations needed to sort the cows. The second line contains $K$ space-separated integers $c_1,c_2,\ldots,c_K$, each in the range $1\ldots N-1$. If in the $i$-th operation, FJ commands the cow facing him to move back $c_i$ steps, then after $K$ operations the cows should be sorted. If there are multiple optimal sequences of operations, your program may output any one of them (though in practice, the solution is unique).

Translated by ChatGPT 5