19914번 - Arranging Shoes 서브태스크다국어언어 제한함수 구현

문제

Adnan owns the biggest shoe store in Baku. A box containing $n$ pairs of shoes has just arrived at the store. Each pair consists of two shoes of the same size: a left and a right one. Adnan has put all of the 2ドルn$ shoes in a row consisting of 2ドルn$ positions numbered 0ドル$ through 2ドルn-1$ from left to right.

Adnan wants to rearrange the shoes into a valid arrangement. An arrangement is valid if and only if for every $i$ (0ドル \leq i \leq n-1$), the following conditions hold:

• The shoes at positions 2ドルi$ and 2ドルi+1$ are of the same size.
• The shoe at position 2ドルi$ is a left shoe.
• The shoe at position 2ドルi+1$ is a right shoe.

For this purpose, Adnan can make a series of swaps.

In each swap, he selects two shoes that are adjacent at that moment and exchanges them (i.e., picks them up and puts each one on the former position of the other shoe).

Two shoes are adjacent if their positions differ by one.

Determine the minimum number of swaps that Adnan needs to perform in order to obtain a valid arrangement of the shoes.

구현

You should implement the following procedure:

int64 count_swaps(int[] S)

• $S$: an array of 2ドルn$ integers. For each $i$ (0ドル \leq i \leq 2n-1$), $|S[i]|$ is a non-zero value equal to the size of the shoe initially placed at position $i$. Here, $|x|$ denotes the absolute value of $x,ドル which equals $x$ if $x>0$ and equals $-x$ if $x<0$. If $S[i] < 0,ドル the shoe at position $i$ is a left shoe; otherwise, it is a right shoe.
• This procedure should return the minimum number of swaps (of adjacent shoes) that need to be performed in order to obtain a valid arrangement.

제한

• 1ドル \leq n \leq 100,000円$
• For each $i$ (0ドル \leq i \leq 2n-1$), 1ドル \leq |S[i]| \leq n$.
• A valid arrangement of the shoes can be obtained by performing some sequence of swaps.

예시 1

Consider the following call:

count_swaps([2, 1, -1, -2])

Adnan can obtain a valid arrangement in 4ドル$ swaps.

For instance, he can first swap shoes 1ドル$ and $-1,ドル then 1ドル$ and $-2,ドル then $-1$ and $-2,ドル and finally 2ドル$ and $-2$. He would then obtain the following valid arrangement: $[-2, 2, -1, 1]$. It is not possible to obtain any valid arrangement with less than 4ドル$ swaps. Therefore, the procedure should return 4ドル$.

예시 2

In the following example, all the shoes have the same size:

count_swaps([-2, 2, 2, -2, -2, 2])

Adnan can swap the shoes at positions 2ドル$ and 3ドル$ to obtain the valid arrangement $[-2, 2, -2, 2, -2, 2],ドル so the procedure should return 1ドル$.

서브태스크

힌트

첨부

• shoes.zip