結果

問題 No.1079 まお
ユーザー sjikisjiki
提出日時 2024-05-09 11:16:29
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,870 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 97,280 KB
最終ジャッジ日時 2024-05-09 11:16:35
合計ジャッジ時間 4,945 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
権限があれば一括ダウンロードができます

ソースコード

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