結果

問題 No.697 池の数はいくつか
ユーザー conf8oconf8o
提出日時 2020-04-30 07:48:45
言語 Swift
(5.10.0)
結果
MLE  
実行時間 -
コード長 4,764 bytes
コンパイル時間 7,050 ms
コンパイル使用メモリ 190,028 KB
実行使用メモリ 824,416 KB
最終ジャッジ日時 2024-11-25 16:07:27
合計ジャッジ時間 54,456 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
187,572 KB
testcase_01 AC 11 ms
22,180 KB
testcase_02 AC 11 ms
122,092 KB
testcase_03 AC 10 ms
15,872 KB
testcase_04 AC 11 ms
15,744 KB
testcase_05 AC 10 ms
15,744 KB
testcase_06 AC 11 ms
15,744 KB
testcase_07 AC 11 ms
15,488 KB
testcase_08 AC 10 ms
15,872 KB
testcase_09 AC 10 ms
15,360 KB
testcase_10 AC 11 ms
15,488 KB
testcase_11 AC 11 ms
15,488 KB
testcase_12 AC 10 ms
15,488 KB
testcase_13 AC 10 ms
15,616 KB
testcase_14 AC 11 ms
15,872 KB
testcase_15 AC 11 ms
15,488 KB
testcase_16 AC 10 ms
15,744 KB
testcase_17 AC 10 ms
15,616 KB
testcase_18 AC 10 ms
16,000 KB
testcase_19 AC 10 ms
15,360 KB
testcase_20 AC 10 ms
15,616 KB
testcase_21 AC 10 ms
15,488 KB
testcase_22 AC 10 ms
15,872 KB
testcase_23 AC 10 ms
15,360 KB
testcase_24 AC 935 ms
26,896 KB
testcase_25 AC 1,990 ms
89,972 KB
testcase_26 AC 3,110 ms
165,160 KB
testcase_27 AC 4,242 ms
91,336 KB
testcase_28 AC 1,546 ms
44,844 KB
testcase_29 MLE -
testcase_30 TLE -
testcase_31 MLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import Foundation

private struct Deque<T> {
    public var buffer: [T?] = [T?](repeating: nil, count: 8)
    private var head: Int
    private var tail: Int

    init() {
        head = 0
        tail = 0
    }

    public var isEmpty: Bool {
        return tail == head
    }

    public var capacity: Int {
        return buffer.count
    }
    
    public var count: Int {
        return (head &- tail) & (capacity - 1)
    }
    
    public var isFull: Bool {
        return capacity - count == 1
    }
    
    
    private func wrapIndex(index: Int, size: Int) -> Int {
        return index & (size - 1)
    }
    
    private func wrapAdd(index: Int, append: Int) -> Int {
        return wrapIndex(index: index &+ append, size: capacity)
    }
    
    private func wrapSub(index: Int, subtrahend: Int) -> Int {
        return wrapIndex(index: index &- subtrahend, size: capacity)
    }

    mutating func growIfNecessary() {
        if isFull {
            let oldCap = capacity
            buffer.append(contentsOf: Array(repeating: nil, count: capacity))
            handleCapacityIncrease(oldCap: oldCap)
        }
    }
    
    private mutating func handleCapacityIncrease(oldCap: Int) {
        let newCap = capacity
        
        //  T      H
        // [ooooooo.]
        //  T      H
        // [ooooooo.........]
        if tail <= head {
            
        }
        //    HT
        // [oo.ooooo]
        //     T      H
        // [...ooooooo......]
        else if head < oldCap - tail {
            buffer.withUnsafeMutableBufferPointer { buf in
                for i in 0...head {
                    buf.swapAt(i, i+oldCap)
                }
            }
            head += oldCap
        }
        //       HT
        // [ooooo.oo]
        //       H        T
        // [ooooo.........oo]
        else {
            let newTail = newCap - (oldCap - tail)
            buffer.withUnsafeMutableBufferPointer { buf in
                for i in tail..<oldCap {
                    buf.swapAt(i, (i-tail)+newTail)
                }
            }
            tail = newTail
        }
    }

    public mutating func pushBack(_ element: T) {
        growIfNecessary()

        let head = self.head
        self.head = wrapAdd(index: self.head, append: 1)
        buffer[head] = element
    }

    public mutating func pushFront(_ element: T) {
        growIfNecessary()

        self.tail = wrapSub(index: self.tail, subtrahend: 1)
        let tail = self.tail
        buffer[tail] = element
    }

    mutating func popBack() -> T? {
        if isEmpty {
            return nil
        } else {
            self.head = wrapSub(index: self.head, subtrahend: 1)
            let head = self.head

            return buffer[head]
        }
        
    }
    
    mutating func popFront() -> T? {
        if isEmpty {
            return nil
        } else {
            let tail = self.tail
            self.tail = wrapAdd(index: self.tail, append: 1)

            return buffer[tail]
        }
        
    }

    func peekFront() -> T? {
        if isEmpty {
            return nil
        } else {
            return buffer[head]
        }
    }

    func peekBack() -> T? {
        if isEmpty {
            return nil
        } else {
            return buffer[tail]
        }
    }
}

func readInt2() -> (Int16, Int16) {
    let l = readLine()!.split(separator: " ").map{Int16($0)!}
    return (l[0], l[1])
}

func readLines(_ n: Int16) -> [[Bool]] {
    return (0..<n).map{(Int16) -> [Bool] in
        return readLine()!.split(separator: " ").map{$0 == "1"}
    }
}

func bfs(_ i: Int16, _ j: Int16, _ grid: inout [[Bool]], _ H: Int16, _ W: Int16) -> Int{
    var frontier = Deque<(Int16, Int16)>()
    frontier.pushBack((i, j))
    let dires: [(Int16, Int16)] = [(-1, 0),(0, 1),(1, 0),(0, -1)]
    while !frontier.isEmpty {
        let (h, w) = frontier.popFront()!
        grid[Int(h)][Int(w)] = false
        for (y, x) in dires {
            let sucY = h+y
            let sucX = w+x
            if sucY < 0 || sucY >= H || sucX < 0 || sucX >= W || !grid[Int(sucY)][Int(sucX)] {
                continue
            }
            frontier.pushBack((sucY, sucX))
        }
    }
    return 1
}

func test() {
    let (H, W): (Int16, Int16) = readInt2()
    var A = readLines(H)
    var ans = 0
    for i in 0..<H {
        for j in 0..<W {
            if !A[Int(i)][Int(j)] {
                continue
            }
            ans += bfs(i, j, &A, H, W)
        }
    }
    print(ans)
    
//    var dq = Deque<Int>()
//    for i in 0..<32 {
//        dq.pushFront(i)
//        print(dq.buffer)
//    }
//
//    print(dq.buffer)
//    for i in 1...16 {
//        print(dq.popFront())
//        print(dq.popBack())
//    }
}

test()
0