CCO '21 P1 - Swap Swap Sort

View as PDF

Points: 17 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem type
Canadian Computing Olympiad: 2021 Day 1, Problem 1

There is an array of integers, each with a value between and . Your friend has an algorithm that can sort this array according to any ordering of the numbers from to . The algorithm performs a sequence of swap operations, that exchange two adjacent elements of the array. The algorithm performs exactly the minimum number of such swaps to sort the array.

The desired ordering of the numbers from to is given by a target permutation. A target permutation is a sequence of each number from to appearing exactly once, in the same order that is desired by the corresponding ordering.

For example, the array [1 4 2 1 2] sorted by the target permutation results in the array [4 1 1 2 2].

You are interested in the number of swaps performed by your friend's algorithm for different target permutations. To explore this, you start with a target permutation of and perform operations on it. Each operation swaps two adjacent elements of the target permutation. After performing each operation, find the number of swaps your friend's algorithm would make if it was run with the current target permutation. The operations cumulatively change the target permutation, but do not affect the array.

Input Specification

The first line contains the three integers , , and .

The next line contains integers specifying the array.

The next lines each contains a single integer , representing the operation of swapping the elements of the target permutation at indices and .

For 3 of the 25 available marks, .

For an additional 3 of the 25 available marks, .

For an additional 5 of the 25 available marks, .

Output Specification

For each of the operations, output a line containing a single integer; the answer for the current target permutation.

Sample Input

5 4 3
1 4 2 1 2
3
2
1

Sample Output

4
2
2

Explanation for Sample Output

The three target permutations are , then , then . For the final target permutation, your friend's algorithm uses two swaps to sort the array [1 4 2 1 2] to [4 1 1 2 2].

Comments

There are no comments at the moment.