Submission #16840108

---

Source Code Expand

import Foundation
// 第一引数に二分探索したい配列を渡す
// 第二引数に検索したい要素を渡す
// 第三引数に二分探索したい配列の大きさを渡す
func binarySearch(list:[Int],item:Int,cnt:Int)->Int{
    // 解の存在範囲を初期化
    var low = -1
    var high = cnt 
    // 解の存在範囲が1より大きい間、繰り返す
    while (high - low > 1) {
        let mid = Int(floor(Double(low + high) / 2))
        if list[mid] >= item {
            // midが条件を満たせば、解の存在範囲は(low,mid]
            high = mid
        } else {
            // midが条件を満たさなければ、解の存在範囲は(mid,high]
            low = mid
        }
    }
    // この時点で、low + 1 = highとなっている
    return high
}

// 標準入力の受け取り
let n = Int(readLine()!)!
var a = readLine()!.split(separator:" ").map{Int($0)!}
var b = readLine()!.split(separator:" ").map{Int($0)!}
var c = readLine()!.split(separator:" ").map{Int($0)!}

// とりあえず各配列をソートする
a.sort { $0 < $1 }
b.sort { $0 < $1 }
c.sort { $0 < $1 }

// 答えを入れる変数を用意
var ans = 0;

// 中部のパーツの配列に対して全探索
for i in b{
    // 各配列に対して二分探索
    let ai = binarySearch(list:a,item:i,cnt:n)
    let ci = binarySearch(list:c,item:i+1,cnt:n)
    
    // ansに考えられるパーツの組み合わせの個数を加える
    ans += (ai)*(n-ci)
}

// 答えを出力
print(ans)

Submission Info

Judge Result