Program time limit: 1 second
Program memory limit: 512 MB
In the kingdom of Numerica, the Grand Bazaar is the highlight of the Odd-Even Festival. Merchants from across the land set up their stalls, each presenting a unique treasure. However, Numerica’s ancient tradition requires these treasures to be arranged in perfect order by the end of the festival.
The stalls are lined up in a single row, numbered from 1 to $N$ . Initially, the treasures are placed in a random order. The festival’s rules dictate a special way in which you can reorder these treasures. This year, the rule is particularly tricky:
The Festival Rules: - You can rearrange the treasures, but only by exchanging them between specific pairs of stalls: two stalls can only swap treasures if one is “next to a tree” and the other is“next to a fountain.” - The stalls alternate between being “next to a tree” and “next to a fountain”.
Your task is to figure out how to place the treasures in ascending order following these rules. If it’s possible, find the minimum number of exchanges needed to accomplish this. If it cannot be done according to the festival’s swapping rules, declare it “IMPOSSIBLE.”
The first line contains an integer $N$, the number of stalls.
The next line contains $N$ integers which is a permutation of $1, 2, \dots, n$, the initial ordering of the treasures.
For all test cases:
If is it possible to sort the permutation with the given constraints, output a single integer, the minimum number of swaps required.
Otherwise, output the string IMPOSSIBLE
.
In Python, you could use the line print(answer)
or print("IMPOSSIBLE")
.
In C or C++, you could use the line printf("%d\n", answer);
or printf("IMPOSSIBLE\n");
.
5
3 4 5 2 1
5
[3, 4, 5, 2, 1]
-> [4, 3, 5, 2, 1]
-> [4, 5, 3, 2, 1]
-> [4, 1, 3, 2, 5]
-> [2, 1, 3, 4, 5]
-> [1, 2, 3, 4, 5]
To sort the permutation with $5$ swaps, we swap values $3$ and $4$, then values $3$ and $5$, then values $1$ and $5$, then values $2$ and $4$, then values $1$ and $2$.
Its not possible to sort the permutation with less than $5$ swaps.
Your program will be run on the 1 sample case and multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves the task. Recall that your final score on the task is the score of your highest scoring submission.
You haven't submitted to this task.