Submission #1161506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161506		6530089	Swap Swap Sort (CCO21_day1problem1)	Pypy 3	3 / 25	5101 ms	287852 KiB

Main

import sys

# Fast input reading
input = sys.stdin.read
data = input().split()
idx = 0

# Read N, K, Q
N, K, Q = map(int, data[idx:idx+3])
idx += 3

# Read array A
A = list(map(int, data[idx:idx+N]))
idx += N

# Read swap queries
swaps = list(map(int, data[idx:idx+Q]))

# Initial target permutation
P = list(range(1, K + 1))  # P[i] represents the target permutation
pos = {P[i]: i for i in range(K)}  # Position of each number in P

# Convert A to the index representation based on P
A_mapped = [pos[x] for x in A]

# Count initial swaps using Merge Sort-based inversion count
def count_inversions(arr):
    def merge_count_split_inv(left, right):
        if len(left) == 0 or len(right) == 0:
            return left + right, 0
        
        merged, count, i, j = [], 0, 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                count += len(left) - i  # Count inversions
                j += 1
        
        merged += left[i:] + right[j:]
        return merged, count

    def sort_and_count(arr):
        if len(arr) <= 1:
            return arr, 0
        mid = len(arr) // 2
        left, left_inv = sort_and_count(arr[:mid])
        right, right_inv = sort_and_count(arr[mid:])
        merged, split_inv = merge_count_split_inv(left, right)
        return merged, left_inv + right_inv + split_inv

    _, inv_count = sort_and_count(arr)
    return inv_count

# Compute the initial inversion count
current_inv = count_inversions(A_mapped)

# Process swap queries efficiently
result = []
for j in swaps:
    # Get the two values being swapped
    v1, v2 = P[j-1], P[j]

    # Get their positions
    idx1, idx2 = pos[v1], pos[v2]

    # Swap them in P
    P[j-1], P[j] = P[j], P[j-1]

    # Swap their positions
    pos[v1], pos[v2] = pos[v2], pos[v1]

    # Only update affected elements in A_mapped
    for i in range(N):
        if A[i] == v1 or A[i] == v2:
            A_mapped[i] = pos[A[i]]

    # Efficiently adjust inversion count (local recalculation)
    current_inv = count_inversions(A_mapped)

    # Store the result
    result.append(str(current_inv))

# Output results efficiently
sys.stdout.write("\n".join(result) + "\n")

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 45%)

=======

• Subtask 1: 0 / 3
• Subtask 2: 3 / 3
• Subtask 3: 0 / 5
• Subtask 4: 0 / 14