結果

問題 No.1021 Children in Classrooms
ユーザー conf8oconf8o
提出日時 2020-04-16 18:11:05
言語 Swift
(5.10.0)
結果
AC  
実行時間 239 ms / 2,000 ms
コード長 39,847 bytes
コンパイル時間 2,903 ms
コンパイル使用メモリ 196,628 KB
実行使用メモリ 25,988 KB
最終ジャッジ日時 2024-05-07 21:08:59
合計ジャッジ時間 6,393 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 11 ms
15,872 KB
testcase_01 AC 11 ms
15,616 KB
testcase_02 AC 11 ms
15,744 KB
testcase_03 AC 12 ms
15,616 KB
testcase_04 AC 13 ms
15,872 KB
testcase_05 AC 12 ms
15,616 KB
testcase_06 AC 13 ms
15,616 KB
testcase_07 AC 13 ms
15,744 KB
testcase_08 AC 12 ms
15,616 KB
testcase_09 AC 225 ms
24,656 KB
testcase_10 AC 228 ms
25,012 KB
testcase_11 AC 229 ms
24,904 KB
testcase_12 AC 220 ms
24,720 KB
testcase_13 AC 225 ms
24,884 KB
testcase_14 AC 226 ms
24,628 KB
testcase_15 AC 177 ms
24,520 KB
testcase_16 AC 174 ms
24,656 KB
testcase_17 AC 183 ms
24,560 KB
testcase_18 AC 239 ms
25,988 KB
testcase_19 AC 25 ms
15,732 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.swift:10:9: warning: initialization of immutable value 'M' was never used; consider replacing with assignment to '_' or removing it
    let M = line[1]
    ~~~~^
    _

ソースコード

diff #

import Foundation

func readInt() -> [Int] {
    return readLine()!.split(separator: " ").map { c in Int(c)! }
}

func main() {
    let line = readInt()
    let N = line[0]
    let M = line[1]
    var deque = Deque<Int>(readInt())
    let S = readLine()!

    for s in S {
        if s == "L" {
            let a = deque.popFirst()!
            let b = deque.popFirst()!
            deque.prepend(a+b)
            deque.append(0)
        } else {
            let a = deque.popLast()!
            let b = deque.popLast()!
            deque.append(a+b)
            deque.prepend(0)
        }
    }

    for _ in 1...N {
        print(deque.popFirst()!, terminator: " ")
    }
    print()
}

// 以下リポジトリより取得
// https://github.com/attaswift/Deque
public struct Deque<Element> {
    /// The storage for this deque.
    internal fileprivate(set) var buffer: DequeBuffer<Element>

    /// Initializes an empty deque.
    public init() {
        buffer = DequeBuffer()
    }

    /// Initializes an empty deque that is able to store at least `minimumCapacity` items without reallocating its storage.
    public init(minimumCapacity: Int) {
        buffer = DequeBuffer(capacity: minimumCapacity)
    }

    /// Initialize a new deque from the elements of any sequence.
    public init<S: Sequence>(_ elements: S) where S.Element == Element {
        self.init(minimumCapacity: elements.underestimatedCount)
        append(contentsOf: elements)
    }

    /// Initialize a deque of `count` elements, each initialized to `repeating`.
    public init(repeating: Element, count: Int) {
        buffer = DequeBuffer(repeating: repeating, count: count)
    }
}

//MARK: Uniqueness and Capacity

extension Deque {
    /// The maximum number of items this deque can store without reallocating its storage.
    /// 
    /// If the deque grows larger than its capacity, it discards its current storage and allocates a larger one.
    public var capacity: Int { return buffer.capacity }

    fileprivate func grow(_ capacity: Int) -> Int {
        guard capacity > self.capacity else { return self.capacity }
        return Swift.max(capacity, 2 * self.capacity)
    }

    /// Ensure that this deque is capable of storing at least `minimumCapacity` items without reallocating its storage.
    public mutating func reserveCapacity(_ minimumCapacity: Int) {
        guard buffer.capacity < minimumCapacity else { return }
        if isKnownUniquelyReferenced(&buffer) {
            buffer = buffer.realloc(minimumCapacity)
        }
        else {
            let new = DequeBuffer<Element>(capacity: minimumCapacity)
            new.insert(contentsOf: buffer, at: 0)
            buffer = new
        }
    }

    internal var isUnique: Bool { mutating get { return isKnownUniquelyReferenced(&buffer) } }

    @inline(__always)
    fileprivate mutating func makeUnique() {
        self.makeUnique(buffer.capacity)
    }

    @inline(__always)
    fileprivate mutating func makeUnique(_ capacity: Int) {
        guard !isUnique || buffer.capacity < capacity else { return }
        let copy = DequeBuffer<Element>(capacity: capacity)

        // Ensure new buffer is indistinguishable from the original in unit tests.
        // This is a workaround for a compiler issue where the pass-by-reference optimization seems to be missing in debug builds.
        copy.start = buffer.start

        copy.insert(contentsOf: buffer, at: 0)
        buffer = copy
    }
}

//MARK: MutableCollection

extension Deque: RandomAccessCollection, MutableCollection {
    public typealias Index = Int
    public typealias Indices = CountableRange<Int>
    public typealias Iterator = IndexingIterator<Deque<Element>>
    #if swift(>=4.1) || (swift(>=3.3) && !swift(>=4.0))
    public typealias SubSequence = Slice<Deque<Element>>
    #else
    public typealias SubSequence = RangeReplaceableRandomAccessSlice<Deque<Element>>
    #endif

    /// The number of elements currently stored in this deque.
    public var count: Int { return buffer.count }

    /// The indices that are valid for subscripting the collection, in ascending order.
    public var indices: CountableRange<Int> {
        return startIndex ..< endIndex
    }

    /// The position of the first element in a non-empty deque (this is always zero).
    public var startIndex: Int { return 0 }

    /// The index after the last element in a non-empty deque (this is always the element count).
    public var endIndex: Int { return count }

    /// Returns the position immediately after the given index.
    public func index(after index: Int) -> Int {
        return index + 1
    }

    /// Returns the position immediately before the given index.
    public func index(before index: Int) -> Int {
        return index - 1
    }

    /// Returns an index that is the specified distance from the given index.
    public func index(_ i: Int, offsetBy n: Int) -> Index {
        return i + n
    }

    /// Replaces the given index with its successor.
    public func formIndex(after index: inout Int) {
        index += 1
    }

    /// Replaces the given index with its predecessor.
    public func formIndex(before index: inout Int) {
        index -= 1
    }

    /// Offsets the given index by the specified distance.
    ///
    /// Advancing an index beyond a collection's ending index or offsetting it
    /// before a collection's starting index will generate an invalid index.
    ///
    /// - Parameters
    ///   - i: A valid index of the collection.
    ///   - n: The distance to offset `i`.
    ///
    /// - SeeAlso: `index(_:offsetBy:)`, `formIndex(_:offsetBy:limitedBy:)`
    /// - Complexity: O(1)
    public func formIndex(_ i: inout Index, offsetBy n: Int) {
        i += n
    }

    /// `true` iff this deque is empty.
    public var isEmpty: Bool { return count == 0 }

    @inline(__always)
    fileprivate func checkSubscript(_ index: Int) {
        precondition(index >= 0 && index < count)
    }

    // Returns or changes the element at `index`.
    public subscript(index: Int) -> Element {
        get {
            checkSubscript(index)
            return buffer[index]
        }
        set(value) {
            checkSubscript(index)
            makeUnique()
            buffer[index] = value
        }
    }

    /// Accesses a contiguous subrange of the collection’s elements.
    public subscript(bounds: Range<Int>) -> SubSequence {
        get {
            return SubSequence(base: self, bounds: bounds)
        }
        set {
            self.replaceSubrange(bounds, with: newValue)
        }
    }
}

//MARK: ArrayLiteralConvertible

extension Deque: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: Element...) {
        self.buffer = DequeBuffer(capacity: elements.count)
        buffer.insert(contentsOf: elements, at: 0)
    }
}

//MARK: CustomStringConvertible

extension Deque: CustomStringConvertible, CustomDebugStringConvertible {
    
    private func makeDescription(debug: Bool) -> String {
        var result = debug ? "\(String(reflecting: Deque.self))([" : "Deque["
        var first = true
        for item in self {
            if first {
                first = false
            } else {
                result += ", "
            }
            if debug {
                debugPrint(item, terminator: "", to: &result)
            }
            else {
                print(item, terminator: "", to: &result)
            }
        }
        result += debug ? "])" : "]"
        return result
    }

    public var description: String {
        return makeDescription(debug: false)
    }
    public var debugDescription: String {
        return makeDescription(debug: true)
    }
}

//MARK: RangeReplaceableCollection

extension Deque: RangeReplaceableCollection {
    /// Replace the given `range` of elements with `newElements`.
    ///
    /// - Complexity: O(`range.count`) if storage isn't shared with another live deque,
    ///   and `range` is a constant distance from the start or the end of the deque; otherwise O(`count + range.count`).
    public mutating func replaceSubrange<C: Collection>(_ range: Range<Int>, with newElements: C) where C.Element == Element {
        precondition(range.lowerBound >= 0 && range.upperBound <= count)
        let newCount: Int = numericCast(newElements.count)
        let delta = newCount - range.count
        if isUnique && count + delta <= capacity {
            buffer.replaceSubrange(range, with: newElements)
        }
        else {
            let b = DequeBuffer<Element>(capacity: grow(count + delta))
            b.insert(contentsOf: self.buffer, subrange: 0 ..< range.lowerBound, at: 0)
            b.insert(contentsOf: newElements, at: b.count)
            b.insert(contentsOf: self.buffer, subrange: range.upperBound ..< count, at: b.count)
            buffer = b
        }
    }

    // Code targeting the Swift 4.1 compiler and below
    #if !(swift(>=4.1.50) || (swift(>=3.4) && !swift(>=4.0)))
    public mutating func replaceSubrange<C: Collection>(_ range: CountableRange<Int>, with newElements: C) where C.Element == Element {
        // This is also defined as a protocol extension on RangeReplaceableCollection. However, using that extension
        // breaks isUnique, leading to extra COW copies. Providing this overload restores COW behavior in static contexts, at least.
        self.replaceSubrange(Range(range), with: newElements)
    }
    #endif

    public mutating func replaceSubrange<C: Collection>(_ range: ClosedRange<Int>, with newElements: C) where C.Element == Element {
        // This is also defined as a protocol extension on RangeReplaceableCollection. However, using that extension
        // breaks isUnique, leading to extra COW copies. Providing this overload restores COW behavior in static contexts, at least.
        self.replaceSubrange(Range(range), with: newElements)
    }

    // Code targeting the Swift 4.1 compiler and below
    #if !(swift(>=4.1.50) || (swift(>=3.4) && !swift(>=4.0)))
    public mutating func replaceSubrange<C: Collection>(_ range: CountableClosedRange<Int>, with newElements: C) where C.Element == Element {
        // This is also defined as a protocol extension on RangeReplaceableCollection. However, using that extension
        // breaks isUnique, leading to extra COW copies. Providing this overload restores COW behavior in static contexts, at least.
        self.replaceSubrange(Range(range), with: newElements)
    }
    #endif

    /// Append `newElement` to the end of this deque.
    ///
    /// - Parameter newElement: The element to append to the deque.
    ///
    /// - Complexity: Appending an element to the deque averages to O(1) over
    ///   many additions. When the deque needs to reallocate storage before
    ///   appending or its storage is shared with another copy, appending an
    ///   element is O(*n*), where *n* is the length of the deque.
    public mutating func append(_ newElement: Element) {
        makeUnique(grow(count + 1))
        buffer.append(newElement)
    }

    /// Appends the elements of a sequence to the end of the deque.
    ///
    /// - Parameter newElements: The elements to append to the deque.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the resulting deque.
    public mutating func append<S: Sequence>(contentsOf newElements: S) where S.Element == Element {
        makeUnique(self.count + newElements.underestimatedCount)
        var capacity = buffer.capacity
        var count = buffer.count
        var iterator = newElements.makeIterator()
        var next = iterator.next()
        while next != nil {
            if capacity == count {
                reserveCapacity(grow(count + 1))
                capacity = buffer.capacity
            }
            var i = buffer.bufferIndex(forDequeIndex: count)
            let p = buffer.elements
            while let element = next, count < capacity {
                p.advanced(by: i).initialize(to: element)
                i += 1
                if i == capacity { i = 0 }
                count += 1
                next = iterator.next()
            }
            buffer.count = count
        }
    }

    /// Insert `newElement` at index `i` into this deque.
    ///
    /// - Complexity: O(`count`). Note though that complexity is O(1) if `i` is of a constant distance from the front or end of the deque.
    public mutating func insert(_ newElement: Element, at i: Int) {
        makeUnique(grow(count + 1))
        buffer.insert(newElement, at: i)
    }

    /// Insert the contents of `newElements` into this deque, starting at index `i`.
    ///
    /// - Complexity: O(`count`). Note though that complexity is O(1) if `i` is of a constant distance from the front or end of the deque.
    public mutating func insert<C: Collection>(contentsOf newElements: C, at i: Int) where C.Element == Element {
        makeUnique(grow(count + numericCast(newElements.count)))
        buffer.insert(contentsOf: newElements, at: i)
    }

    /// Remove the element at a given index from this deque.
    ///
    /// - Complexity: O(`count`). Note though that complexity is O(1) if `index` is of a constant distance from the front or end of the deque.
    @discardableResult
    public mutating func remove(at index: Int) -> Element {
        checkSubscript(index)
        makeUnique()
        let element = buffer[index]
        buffer.removeSubrange(index ..< index + 1)
        return element
    }

    /// Remove and return the first element from this deque.
    ///
    /// - Requires: `count > 0`
    /// - Complexity: O(1) if storage isn't shared with another live deque; otherwise O(`count`).
    @discardableResult
    public mutating func removeFirst() -> Element {
        precondition(count > 0)
        makeUnique()
        return buffer.popFirst()!
    }

    /// Remove the first `n` elements from this deque.
    ///
    /// - Requires: `count >= n`
    /// - Complexity: O(`n`) if storage isn't shared with another live deque; otherwise O(`count`).
    public mutating func removeFirst(_ n: Int) {
        precondition(count >= n)
        makeUnique()
        buffer.removeSubrange(0 ..< n)
    }

    /// Remove the first `n` elements from this deque.
    ///
    /// - Requires: `count >= n`
    /// - Complexity: O(`n`) if storage isn't shared with another live deque; otherwise O(`count`).
    public mutating func removeSubrange(_ range: Range<Int>) {
        precondition(range.lowerBound >= 0 && range.upperBound <= count)
        makeUnique()
        buffer.removeSubrange(range)
    }

    @available(*, deprecated, renamed: "removeAll(keepingCapacity:)")
    public mutating func removeAll(keepCapacity: Bool) {
        self.removeAll(keepingCapacity: keepCapacity)
    }

    /// Remove all elements from this deque.
    ///
    /// - Complexity: O(`count`).
    public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
        makeUnique()
        if keepCapacity {
            buffer.removeSubrange(0..<count)
        }
        else {
            buffer = DequeBuffer()
        }
    }
}

//MARK: Miscellaneous mutators
extension Deque {
    /// Remove and return the last element from this deque.
    ///
    /// - Requires: `count > 0`
    /// - Complexity: O(1) if storage isn't shared with another live deque; otherwise O(`count`).
    @discardableResult
    public mutating func removeLast() -> Element {
        precondition(count > 0)
        makeUnique()
        return buffer.popLast()!
    }

    /// Remove and return the last `n` elements from this deque.
    ///
    /// - Requires: `count >= n`
    /// - Complexity: O(`n`) if storage isn't shared with another live deque; otherwise O(`count`).
    public mutating func removeLast(_ n: Int) {
        let c = count
        precondition(c >= n)
        makeUnique()
        buffer.removeSubrange(c - n ..< c)
    }

    /// Remove and return the first element if the deque isn't empty; otherwise return nil.
    ///
    /// - Complexity: O(1) if storage isn't shared with another live deque; otherwise O(`count`).
    @discardableResult
    public mutating func popFirst() -> Element? {
        makeUnique()
        return buffer.popFirst()
    }

    /// Remove and return the last element if the deque isn't empty; otherwise return nil.
    ///
    /// - Complexity: O(1) if storage isn't shared with another live deque; otherwise O(`count`).
    @discardableResult
    public mutating func popLast() -> Element? {
        makeUnique()
        return buffer.popLast()
    }

    /// Prepend `newElement` to the front of this deque.
    ///
    /// - Complexity: Amortized O(1) if storage isn't shared with another live deque; otherwise O(count).
    public mutating func prepend(_ element: Element) {
        makeUnique(grow(count + 1))
        buffer.prepend(element)
    }
}

//MARK: Equality operators

func == <Element: Equatable>(a: Deque<Element>, b: Deque<Element>) -> Bool {
    let count = a.count
    if count != b.count { return false }
    if count == 0 || a.buffer === b.buffer { return true }

    var agen = a.makeIterator()
    var bgen = b.makeIterator()
    while let anext = agen.next() {
        let bnext = bgen.next()
        if anext != bnext { return false }
    }
    return true
}

func != <Element: Equatable>(a: Deque<Element>, b: Deque<Element>) -> Bool {
    return !(a == b)
}

//MARK: DequeBuffer

/// Storage buffer for a deque.
final class DequeBuffer<Element> {
    /// Pointer to allocated storage.
    internal fileprivate(set) var elements: UnsafeMutablePointer<Element>
    /// The capacity of this storage buffer.
    internal let capacity: Int
    /// The number of items currently in this deque.
    internal fileprivate(set) var count: Int
    /// The index of the first item.
    internal fileprivate(set) var start: Int

    internal init(capacity: Int = 16) {
        // TODO: It would be nicer if element storage was tail-allocated after this instance.
        // ManagedBuffer is supposed to do that, but ManagedBuffer is surprisingly slow. :-/
        self.elements = UnsafeMutablePointer.allocate(capacity: capacity)
        self.capacity = capacity
        self.count = 0
        self.start = 0
    }

    internal convenience init(repeating: Element, count: Int) {
        self.init(capacity: count)
        let p = elements
        self.count = count
        var q = p
        let limit = p + count
        while q != limit {
            q.initialize(to: repeating)
            q += 1
        }
    }

    deinit {
        let p = self.elements
        if start + count <= capacity {
            p.advanced(by: start).deinitialize(count: count)
        }
        else {
            let c = capacity - start
            p.advanced(by: start).deinitialize(count: c)
            p.deinitialize(count: count - c)
        }
        #if swift(>=4.1) || (swift(>=3.3) && !swift(>=4.0))
        p.deallocate()
        #else
        p.deallocate(capacity: capacity)
        #endif
    }

    internal func realloc(_ capacity: Int) -> DequeBuffer {
        if capacity <= self.capacity { return self }
        let buffer = DequeBuffer(capacity: capacity)
        buffer.count = self.count
        let dst = buffer.elements
        let src = self.elements
        if self.start + self.count <= self.capacity {
            dst.moveInitialize(from: src.advanced(by: start), count: count)
        }
        else {
            let c = self.capacity - self.start
            dst.moveInitialize(from: src.advanced(by: self.start), count: c)
            dst.advanced(by: c).moveInitialize(from: src, count: self.count - c)
        }
        self.count = 0
        return buffer
    }


    /// Returns the storage buffer index for a deque index.
    internal func bufferIndex(forDequeIndex index: Int) -> Int {
        let i = start + index
        if i >= capacity { return i - capacity }
        if i < 0 { return i + capacity }
        return i
    }

    /// Returns the deque index for a storage buffer index.
    internal func dequeIndex(forBufferIndex i: Int) -> Int {
        if i >= start {
            return i - start
        }
        return capacity - start + i
    }

    internal var isFull: Bool { return count == capacity }

    internal subscript(index: Int) -> Element {
        get {
            assert(index >= 0 && index < count)
            let i = bufferIndex(forDequeIndex: index)
            return elements.advanced(by: i).pointee
        }
        set {
            assert(index >= 0 && index < count)
            let i = bufferIndex(forDequeIndex: index)
            elements.advanced(by: i).pointee = newValue
        }
    }

    internal func prepend(_ element: Element) {
        precondition(count < capacity)
        let i = start == 0 ? capacity - 1 : start - 1
        elements.advanced(by: i).initialize(to: element)
        self.start = i
        self.count += 1
    }

    @discardableResult
    internal func popFirst() -> Element? {
        guard count > 0 else { return nil }
        let first = elements.advanced(by: start).move()
        self.start = bufferIndex(forDequeIndex: 1)
        self.count -= 1
        return first
    }

    internal func append(_ element: Element) {
        precondition(count < capacity)
        let endIndex = bufferIndex(forDequeIndex:count)
        elements.advanced(by: endIndex).initialize(to: element)
        self.count += 1
    }

    @discardableResult
    internal func popLast() -> Element? {
        guard count > 0 else { return nil }
        let lastIndex = bufferIndex(forDequeIndex: count - 1)
        let last = elements.advanced(by: lastIndex).move()
        self.count -= 1
        return last
    }

    /// Create a gap of `length` uninitialized slots starting at `index`.
    /// Existing elements are moved out of the way.
    /// You are expected to fill the gap by initializing all slots in it after calling this method.
    /// Note that all previously calculated buffer indexes are invalidated by this method.
    fileprivate func openGap(at index: Int, length: Int) {
        assert(index >= 0 && index <= self.count)
        assert(count + length <= capacity)
        guard length > 0 else { return }
        let i = bufferIndex(forDequeIndex: index)
        if index >= (count + 1) / 2 {
            // Make room by sliding elements at/after index to the right
            let end = start + count <= capacity ? start + count : start + count - capacity
            if i <= end { // Elements after index are not yet wrapped
                if end + length <= capacity { // Neither gap nor elements after it will be wrapped
                    // ....ABCD̲EF......
                    elements.advanced(by: i + length).moveInitialize(from: elements.advanced(by: i), count: end - i)
                    // ....ABC.̲..DEF...
                }
                else if i + length <= capacity { // Elements after gap will be wrapped
                    // .........ABCD̲EF. (count = 3)
                    elements.moveInitialize(from: elements.advanced(by: capacity - length), count: end + length - capacity)
                    // EF.......ABCD̲...
                    elements.advanced(by: i + length).moveInitialize(from: elements.advanced(by: i), count: capacity - i - length)
                    // EF.......ABC.̲..D
                }
                else { // Gap will be wrapped
                    // .........ABCD̲EF. (count = 5)
                    elements.advanced(by: i + length - capacity).moveInitialize(from: elements.advanced(by: i), count: end - i)
                    // .DEF.....ABC.̲...
                }
            }
            else { // Elements after index are already wrapped
                if i + length <= capacity { // Gap will not be wrapped
                    // F.......ABCD̲E (count = 1)
                    elements.advanced(by: length).moveInitialize(from: elements, count: end)
                    // .F......ABCD̲E
                    elements.moveInitialize(from: elements.advanced(by: capacity - length), count: length)
                    // EF......ABCD̲.
                    elements.advanced(by: i + length).moveInitialize(from: elements.advanced(by: i), count: capacity - i - length)
                    // EF......ABC.̲D
                }
                else { // Gap will be wrapped
                    // F.......ABCD̲E (count = 3)
                    elements.advanced(by: length).moveInitialize(from: elements, count: end)
                    // ...F....ABCD̲E
                    elements.advanced(by: i + length - capacity).moveInitialize(from: elements.advanced(by: i), count: capacity - i)
                    // .DEF....ABC.̲.
                }
            }
            count += length
        }
        else {
            // Make room by sliding elements before index to the left, updating `start`.
            if i >= start { // Elements before index are not yet wrapped.
                if start >= length { // Neither gap nor elements before it will be wrapped.
                    // ....ABCD̲EF...
                    elements.advanced(by: start - length).moveInitialize(from: elements.advanced(by: start), count: i - start)
                    // .ABC...D̲EF...
                }
                else if i >= length { // Elements before the gap will be wrapped.
                    // ..ABCD̲EF....
                    elements.advanced(by: capacity + start - length).moveInitialize(from: elements.advanced(by: start), count: length - start)
                    // ...BCD̲EF...A
                    elements.moveInitialize(from: elements.advanced(by: length), count: i - length)
                    // BC...D̲EF...A
                }
                else { // Gap will be wrapped
                    // .ABCD̲EF....... (count = 5)
                    elements.advanced(by: capacity + start - length).moveInitialize(from: elements.advanced(by: start), count: i - start)
                    // ....D̲EF...ABC.
                }
            }
            else { // Elements before index are already wrapped.
                if i >= length { // Gap will not be wrapped.
                    // BCD̲EF......A (count = 1)
                    elements.advanced(by: start - length).moveInitialize(from: elements.advanced(by: start), count: capacity - start)
                    // BCD̲EF.....A.
                    elements.advanced(by: capacity - length).moveInitialize(from: elements, count: length)
                    // .CD̲EF.....AB
                    elements.moveInitialize(from: elements.advanced(by: i - length), count: i - length)
                    // C.D̲EF.....AB
                }
                else { // Gap will be wrapped.
                    // CD̲EF......AB
                    elements.advanced(by: start - length).moveInitialize(from: elements.advanced(by: start), count: capacity - start)
                    // CD̲EF...AB...
                    elements.advanced(by: capacity - length).moveInitialize(from: elements, count: i)
                    // .D̲EF...ABC..
                }
            }
            start = start < length ? capacity + start - length : start - length
            count += length
        }
    }

    internal func insert(_ element: Element, at index: Int) {
        precondition(index >= 0 && index <= count && !isFull)
        openGap(at: index, length: 1)
        let i = bufferIndex(forDequeIndex: index)
        elements.advanced(by: i).initialize(to: element)
    }

    internal func insert(contentsOf buffer: DequeBuffer, at index: Int) {
        self.insert(contentsOf: buffer, subrange: 0 ..< buffer.count, at: index)
    }

    internal func insert(contentsOf buffer: DequeBuffer, subrange: Range<Int>, at index: Int) {
        assert(buffer !== self)
        assert(index >= 0 && index <= count)
        assert(count + subrange.count <= capacity)
        assert(subrange.lowerBound >= 0 && subrange.upperBound <= buffer.count)
        guard subrange.count > 0 else { return }
        openGap(at:
            index, length: subrange.count)

        let dp = self.elements
        let sp = buffer.elements

        let dstStart = self.bufferIndex(forDequeIndex: index)
        let srcStart = buffer.bufferIndex(forDequeIndex: subrange.lowerBound)

        let srcCount = subrange.count

        let dstEnd = self.bufferIndex(forDequeIndex: index + srcCount)
        let srcEnd = buffer.bufferIndex(forDequeIndex: subrange.upperBound)

        if srcStart < srcEnd && dstStart < dstEnd {
            dp.advanced(by: dstStart).initialize(from: sp.advanced(by: srcStart), count: srcCount)
        }
        else if dstStart < dstEnd {
            let t = buffer.capacity - srcStart
            dp.advanced(by: dstStart).initialize(from: sp.advanced(by: srcStart), count: t)
            dp.advanced(by: dstStart + t).initialize(from: sp, count: srcCount - t)
        }
        else if srcStart < srcEnd {
            let t = self.capacity - dstStart
            dp.advanced(by: dstStart).initialize(from: sp.advanced(by: srcStart), count: t)
            dp.initialize(from: sp.advanced(by: srcStart + t), count: srcCount - t)
        }
        else {
            let st = buffer.capacity - srcStart
            let dt = self.capacity - dstStart

            if dt < st {
                dp.advanced(by: dstStart).initialize(from: sp.advanced(by: srcStart), count: dt)
                dp.initialize(from: sp.advanced(by: srcStart + dt), count: st - dt)
                dp.advanced(by: st - dt).initialize(from: sp, count: srcCount - st)
            }
            else if dt > st {
                dp.advanced(by: dstStart).initialize(from: sp.advanced(by: srcStart), count: st)
                dp.advanced(by: dstStart + st).initialize(from: sp, count: dt - st)
                dp.initialize(from: sp.advanced(by: dt - st), count: srcCount - dt)
            }
            else {
                dp.advanced(by: dstStart).initialize(from: sp.advanced(by: srcStart), count: st)
                dp.initialize(from: sp, count: srcCount - st)
            }
        }
    }

    internal func insert<C: Collection>(contentsOf collection: C, at index: Int) where C.Element == Element {
        assert(index >= 0 && index <= count)
        let c: Int = numericCast(collection.count)
        assert(count + c <= capacity)
        guard c > 0 else { return }
        openGap(at: index, length: c)
        var q = elements.advanced(by: bufferIndex(forDequeIndex: index))
        let limit = elements.advanced(by: capacity)
        for element in collection {
            q.initialize(to: element)
            q = q.successor()
            if q == limit {
                q = elements
            }
        }
    }

    /// Destroy elements in the range (index ..< index + count) and collapse the gap by moving remaining elements.
    /// Note that all previously calculated buffer indexes are invalidated by this method.
    fileprivate func removeSubrange(_ range: Range<Int>) {
        assert(range.lowerBound >= 0)
        assert(range.upperBound <= self.count)
        guard range.count > 0 else { return }
        let rc = range.count
        let p = elements
        let i = bufferIndex(forDequeIndex: range.lowerBound)
        let j = i + rc <= capacity ? i + rc : i + rc - capacity

        // Destroy items in collapsed range
        if i <= j {
            // ....ABC̲D̲E̲FG...
            p.advanced(by: i).deinitialize(count: rc)
            // ....AB...FG...
        }
        else {
            // D̲E̲FG.......ABC̲
            p.advanced(by: i).deinitialize(count: capacity - i)
            // D̲E̲FG.......AB.
            p.deinitialize(count: j)
            // ..FG.......AB.
        }

        if count - range.lowerBound - rc < range.lowerBound {
            let end = start + count < capacity ? start + count : start + count - capacity

            // Slide trailing items to the left
            if i <= end { // No wrap anywhere after start of collapsed range
                // ....AB.̲..CD...
                p.advanced(by: i).moveInitialize(from: p.advanced(by: i + rc), count: end - i - rc)
                // ....ABC̲D......
            }
            else if i + rc > capacity { // Collapsed range is wrapped
                if end <= rc { // Result will not be wrapped
                    // .CD......AB.̲..
                    p.advanced(by: i).moveInitialize(from: p.advanced(by: i + rc - capacity), count: capacity + end - i - rc)
                    // .........ABC̲D.
                }
                else { // Result will remain wrapped
                    // .CDEFG...AB.̲..
                    p.advanced(by: i).moveInitialize(from: p.advanced(by: i + rc - capacity), count: capacity - i)
                    // ....FG...ABC̲DE
                    p.moveInitialize(from: p.advanced(by: rc), count: end - rc)
                    // FG.......ABC̲DE
                }
            }
            else { // Wrap is after collapsed range
                if end <= rc { // Result will not be wrapped
                    // D.......AB.̲..C
                    p.advanced(by: i).moveInitialize(from: p.advanced(by: i + rc), count: capacity - i - rc)
                    // D.......ABC̲...
                    p.advanced(by: capacity - rc).moveInitialize(from: p, count: end)
                    // ........ABC̲D..
                }
                else { // Result will remain wrapped
                    // DEFG....AB.̲..C
                    p.advanced(by: i).moveInitialize(from: p.advanced(by: i + rc), count: capacity - i - rc)
                    // DEFG....ABC̲...
                    p.advanced(by: capacity - rc).moveInitialize(from: p, count: rc)
                    // ...G....ABC̲DEF
                    p.moveInitialize(from: p.advanced(by: rc), count: end - rc)
                    // G.......ABC̲DEF
                }
            }
            count -= rc
        }
        else {
            // Slide preceding items to the right
            if j >= start { // No wrap anywhere before end of collapsed range
                // ...AB...C̲D...
                p.advanced(by: start + rc).moveInitialize(from: p.advanced(by: start), count: j - start - rc)
                // ......ABC̲D...
            }
            else if j < rc { // Collapsed range is wrapped
                if  start + rc >= capacity  { // Result will not be wrapped
                    // ...C̲D.....AB..
                    p.advanced(by: start + rc - capacity).moveInitialize(from: p.advanced(by: start), count: capacity + j - start - rc)
                    // .ABC̲D.........
                }
                else { // Result will remain wrapped
                    // ..E̲F.....ABCD..
                    p.moveInitialize(from: p.advanced(by: capacity - rc), count: j)
                    // CDE̲F.....AB....
                    p.advanced(by: start + rc).moveInitialize(from: p.advanced(by: start), count: capacity - start - rc)
                    // CDE̲F.........AB
                }
            }
            else { // Wrap is before collapsed range
                if capacity - start <= rc { // Result will not be wrapped
                    // CD...E̲F.....AB
                    p.advanced(by: rc).moveInitialize(from: p, count: j - rc)
                    // ...CDE̲F.....AB
                    p.advanced(by: start + rc - capacity).moveInitialize(from: p.advanced(by: start), count: capacity - start)
                    // .ABCDE̲F.......
                }
                else { // Result will remain wrapped
                    // EF...G̲H...ABCD
                    p.advanced(by: rc).moveInitialize(from: p, count: j - rc)
                    // ...EFG̲H...ABCD
                    p.moveInitialize(from: p.advanced(by: capacity) - rc, count: rc)
                    // BCDEFG̲H...A...
                    p.advanced(by: start + rc).moveInitialize(from: p.advanced(by: start), count: capacity - start - rc)
                    // BCDEFG̲H......A
                }
            }
            start = (start + rc < capacity ? start + rc : start + rc - capacity)
            count -= rc
        }
    }

    internal func replaceSubrange<C: Collection>(_ range: Range<Int>, with newElements: C) where C.Element == Element {
        let newCount: Int = numericCast(newElements.count)
        let delta = newCount - range.count
        assert(count + delta < capacity)
        let common = min(range.count, newCount)
        if common > 0 {
            let p = elements
            var q = p.advanced(by: bufferIndex(forDequeIndex: range.lowerBound))
            let limit = p.advanced(by: capacity)
            var i = common
            for element in newElements {
                q.pointee = element
                q = q.successor()
                if q == limit { q = p }
                i -= 1
                if i == 0 { break }
            }
        }
        if range.count > common {
            removeSubrange(range.lowerBound + common ..< range.upperBound)
        }
        else if newCount > common {
            openGap(at: range.lowerBound + common, length: newCount - common)
            let p = elements
            var q = p.advanced(by: bufferIndex(forDequeIndex: range.lowerBound + common))
            let limit = p.advanced(by: capacity)
            var i = newElements.index(newElements.startIndex, offsetBy: numericCast(common))
            while i != newElements.endIndex {
                q.initialize(to: newElements[i])
                newElements.formIndex(after: &i)
                q = q.successor()
                if q == limit { q = p }
            }
        }
    }
}

//MARK:

extension DequeBuffer {
    internal func forEach(_ body: (Element) throws -> ()) rethrows {
        if start + count <= capacity {
            var p = elements + start
            for _ in 0 ..< count {
                try body(p.pointee)
                p += 1
            }
        }
        else {
            var p = elements + start
            for _ in start ..< capacity {
                try body(p.pointee)
                p += 1
            }
            p = elements
            for _ in 0 ..< start + count - capacity {
                try body(p.pointee)
                p += 1
            }
        }
    }
}

extension Deque {
    public func forEach(_ body: (Element) throws -> ()) rethrows {
        try withExtendedLifetime(buffer) { buffer in
            try buffer.forEach(body)
        }
    }

    public func map<T>(_ transform: (Element) throws -> T) rethrows -> [T] {
        var result: [T] = []
        result.reserveCapacity(self.count)
        try self.forEach { result.append(try transform($0)) }
        return result
    }

    public func flatMap<T>(_ transform: (Element) throws -> T?) rethrows -> [T] {
        var result: [T] = []
        try self.forEach {
            if let r = try transform($0) {
                result.append(r)
            }
        }
        return result
    }

    public func flatMap<S: Sequence>(_ transform: (Element) throws -> S) rethrows -> [S.Element] {
        var result: [S.Element] = []
        try self.forEach {
            result.append(contentsOf: try transform($0))
        }
        return result
    }

    public func filter(_ includeElement: (Element) throws -> Bool) rethrows -> [Element] {
        var result: [Element] = []
        try self.forEach {
            if try includeElement($0) {
                result.append($0)
            }
        }
        return result
    }

    public func reduce<T>(_ initial: T, combine: (T, Element) throws -> T) rethrows -> T {
        var result = initial
        try self.forEach {
            result = try combine(result, $0)
        }
        return result
    }
}

main()
0