結果

問題 No.1015 おつりは要らないです
コンテスト
ユーザー conf8o
提出日時 2020-04-17 15:09:11
言語 Swift
(6.0.3)
結果
WA  
実行時間 -
コード長 4,815 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,896 ms
コンパイル使用メモリ 186,864 KB
実行使用メモリ 21,792 KB
最終ジャッジ日時 2024-11-30 17:29:29
合計ジャッジ時間 5,700 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 WA * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.swift:9:9: warning: initialization of immutable value 'N' was never used; consider replacing with assignment to '_' or removing it
    let N = line[0]
    ~~~~^
    _

ソースコード

diff #
raw source code 

import Foundation

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

func main() {
    let line = readInt()
    let N = line[0]
    var X = line[1]
    var Y = line[2]
    var Z = line[3]

    var A = Heap<Int>(array: readInt(), sort: >)

    while var a = A.remove() {
        guard X+Y+Z > 0 else {
          print("No")
          return
        } 
        if X > 0 {
            if a > 10000 {
                let need = (a+10000) / 10000
                if need > X {
                    a -= X*10000
                    X = 0
                    A.insert(a)
                } else {
                    X = (X*10000 - a) / 10000
                }
            } else {
                X -= 1
            }
        } else if Y > 0 {
            if a > 5000 {
                let need = (a+5000) / 5000
                if need > Y {
                    a -= Y*5000
                    Y = 0
                    A.insert(a)
                } else {
                    Y = (Y*5000 - a) / 5000
                }
            } else {
                Y -= 1
            }
        } else if Z > 0 {
            if a > 1000 {
                let need = (a+1000) / 1000
                if need > Z {
                    a -= Z*1000
                    Z = 0
                    A.insert(a)
                } else {
                    Z = (Z*1000 - a) / 1000
                }
            } else {
                Z -= 1
            }
        }
    }
    
    print("Yes")

}

struct Heap<T> {
  
  var nodes = [T]()
 
  private var orderCriteria: (T, T) -> Bool

  init(sort: @escaping (T, T) -> Bool) {
    self.orderCriteria = sort
  }

  init(array: [T], sort: @escaping (T, T) -> Bool) {
    self.orderCriteria = sort
    configureHeap(from: array)
  }
  
  private mutating func configureHeap(from array: [T]) {
    nodes = array
    for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
      shiftDown(i)
    }
  }
  
  var isEmpty: Bool {
    return nodes.isEmpty
  }
  
  var count: Int {
    return nodes.count
  }
  
  @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
    return (i - 1) / 2
  }

  @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
    return 2*i + 1
  }

  @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
    return 2*i + 2
  }

  func peek() -> T? {
    return nodes.first
  }
  

  mutating func insert(_ value: T) {
    nodes.append(value)
    shiftUp(nodes.count - 1)
  }
  
  mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
    for value in sequence {
      insert(value)
    }
  }

  mutating func replace(index i: Int, value: T) {
    guard i < nodes.count else { return }
    
    remove(at: i)
    insert(value)
  }
 
  @discardableResult mutating func remove() -> T? {
    guard !nodes.isEmpty else { return nil }
    
    if nodes.count == 1 {
      return nodes.removeLast()
    } else {
      let value = nodes[0]
      nodes[0] = nodes.removeLast()
      shiftDown(0)
      return value
    }
  }

  @discardableResult mutating func remove(at index: Int) -> T? {
    guard index < nodes.count else { return nil }
    
    let size = nodes.count - 1
    if index != size {
      nodes.swapAt(index, size)
      shiftDown(from: index, until: size)
      shiftUp(index)
    }
    return nodes.removeLast()
  }

  internal mutating func shiftUp(_ index: Int) {
    var childIndex = index
    let child = nodes[childIndex]
    var parentIndex = self.parentIndex(ofIndex: childIndex)
    
    while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
      nodes[childIndex] = nodes[parentIndex]
      childIndex = parentIndex
      parentIndex = self.parentIndex(ofIndex: childIndex)
    }
    
    nodes[childIndex] = child
  }

  internal mutating func shiftDown(from index: Int, until endIndex: Int) {
    let leftChildIndex = self.leftChildIndex(ofIndex: index)
    let rightChildIndex = leftChildIndex + 1

    var first = index
    if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
      first = leftChildIndex
    }
    if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
      first = rightChildIndex
    }
    if first == index { return }
    
    nodes.swapAt(index, first)
    shiftDown(from: first, until: endIndex)
  }
  
  internal mutating func shiftDown(_ index: Int) {
    shiftDown(from: index, until: nodes.count)
  }
  
}

extension Heap where T: Equatable {
  
  func firstIndex(of node: T) -> Int? {
    return nodes.firstIndex(where: { $0 == node })
  }
  
  @discardableResult mutating func remove(node: T) -> T? {
    if let index = firstIndex(of: node) {
      return remove(at: index)
    }
    return nil
  }
  
}

main()
0