結果

問題 No.1079 まお
コンテスト
ユーザー sjiki
提出日時 2024-05-09 11:16:29
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,870 bytes
コンパイル時間 508 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 97,260 KB
最終ジャッジ日時 2024-12-15 23:40:14
合計ジャッジ時間 4,581 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.read

def merge_count_split_inv(arr, temp_arr, left, mid, right):
    i = left    # 左部分配列の開始インデックス
    j = mid + 1 # 右部分配列の開始インデックス
    k = left    # 仮配列の開始インデックス
    inv_count = 0
  
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            i += 1
        else:
            temp_arr[k] = arr[j]
            inv_count += (mid-i + 1)
            j += 1
        k += 1
  
    while i <= mid:
        temp_arr[k] = arr[i]
        i += 1
        k += 1
  
    while j <= right:
        temp_arr[k] = arr[j]
        j += 1
        k += 1
  
    for i in range(left, right + 1):
        arr[i] = temp_arr[i]
          
    return inv_count
  
def merge_sort_and_count(arr, temp_arr, left, right):
    inv_count = 0
    if left < right:
        mid = (left + right)//2
        inv_count += merge_sort_and_count(arr, temp_arr, left, mid)
        inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right)
        inv_count += merge_count_split_inv(arr, temp_arr, left, mid, right)
    return inv_count

def main():
    data = input().split()
    N = int(data[0])
    balls = []
    index = 1
    for _ in range(2 * N):
        a_i = int(data[index])
        c_i = data[index + 1]
        balls.append((a_i, c_i))
        index += 2
    
    white_indices = []
    black_indices = []
    
    for number, color in balls:
        if color == 'W':
            white_indices.append(number)
        else:
            black_indices.append(number)
    
    temp_white = [0]*N
    temp_black = [0]*N
    white_inv = merge_sort_and_count(white_indices, temp_white, 0, N-1)
    black_inv = merge_sort_and_count(black_indices, temp_black, 0, N-1)
    
    print(white_inv + black_inv)

if __name__ == "__main__":
    main()
0