結果

問題 No.2927 Reverse Polish Equation
ユーザー ID 21712
提出日時 2025-03-20 00:17:29
言語 Go
(1.23.4)
結果
AC  
実行時間 199 ms / 2,000 ms
コード長 3,368 bytes
コンパイル時間 11,791 ms
コンパイル使用メモリ 252,316 KB
実行使用メモリ 14,668 KB
最終ジャッジ日時 2025-03-20 00:17:48
合計ジャッジ時間 17,632 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import . "fmt"
import . "os"
import bf "bufio"
func main() {
    rd := bf.NewReader(Stdin)
    var q int
    var y int64
    Fscan(rd, &q, &y)
    a := make([]Node, 0, q)
    for i := 0; i < q; i++ {
        var s string
        Fscan(rd, &s)
        switch s {
            case "+":
                p := len(a)-1
                a[p-1] = opSum(a[p-1], a[p])
                a = a[:p]
            case "max":
                p := len(a)-1
                a[p-1] = opMax(a[p-1], a[p])
                a = a[:p]
            case "min":
                p := len(a)-1
                a[p-1] = opMin(a[p-1], a[p])
                a = a[:p]
            case "X":
                a = append(a, &Value{1, 0})
            default:
                var c int64
                Sscan(s, &c)
                a = append(a, &Value{0, c})
        }
    }
    var lower, upper int64 = -1, y+1
    for lower+1<upper {
        middle := (lower+upper)/2
        value := a[0].Calc(middle)
        if value < y {
            lower = middle
        } else {
            upper = middle
        }
    }
    if a[0].Calc(upper) == y {
        Println(upper)
    } else {
        Println(-1)
    }
}
type Node interface {
    Calc(x int64) int64
}
type Value struct {
    k, c int64
}
func (v *Value) Calc(x int64) int64 {
    return v.k*x+v.c
}
func (v *Value) Add(other *Value) {
    v.k += other.k
    v.c += other.c
}
func (v *Value) LessThan(other *Value) bool {
    return v.k <= other.k && v.c <= other.c
}
func (v *Value) GreaterThan(other *Value) bool {
    return v.k >= other.k && v.c >= other.c
}
type OpSum struct {
    value Value
    ns []Node
}
func (op *OpSum) Calc(x int64) int64 {
    sum := op.value.Calc(x)
    for _, n := range op.ns {
        sum += n.Calc(x)
    }
    return sum
}
func (op *OpSum) Append(ns ...Node) {
    for _, n := range ns {
        switch w := n.(type) {
            case *Value:
                op.value.Add(w)
            case *OpSum:
                op.value.Add(&w.value)
                op.ns = append(op.ns, w.ns...)
            default:
                op.ns = append(op.ns, n)
        }
    }
}
type OpMin struct {
    ns []Node
}
func (op *OpMin) Calc(x int64) int64 {
    res := op.ns[0].Calc(x)
    for _, n := range op.ns[1:] {
        tmp := n.Calc(x)
        if tmp < res {
            res = tmp
        }
    }
    return res
}
type OpMax struct {
    ns []Node
}
func (op *OpMax) Calc(x int64) int64 {
    res := op.ns[0].Calc(x)
    for _, n := range op.ns[1:] {
        tmp := n.Calc(x)
        if tmp > res {
            res = tmp
        }
    }
    return res
}
func opSum(n1, n2 Node) Node {
    if v1, v1ok := n1.(*Value); v1ok {
        if v2, v2ok := n2.(*Value); v2ok {
            v1.Add(v2)
            return v1
        }
    }
    if s1, s1ok := n1.(*OpSum); s1ok {
        s1.Append(n2)
        return s1
    }
    if s2, s2ok := n2.(*OpSum); s2ok {
        s2.Append(n1)
        return s2
    }
    op := new(OpSum)
    op.Append(n1, n2)
    return op
}
func opMin(n1, n2 Node) Node {
    if v1, v1ok := n1.(*Value); v1ok {
        if v2, v2ok := n2.(*Value); v2ok {
            if v1.LessThan(v2) {
                return v1
            } else if v2.LessThan(v1) {
                return v2
            }
        }
    }
    if m1, m1ok := n1.(*OpMin); m1ok {
        if m2, m2ok := n2.(*OpMin); m2ok {
            m1.ns = append(m1.ns, m2.ns...)
        } else {
            m1.ns = append(m1.ns, n2)
        }
        return m1
    }
    if m2, m2ok := n2.(*OpMin); m2ok {
        m2.ns = append(m2.ns, n1)
        return m2
    }
    return &OpMin{ []Node{n1, n2} }
}
func opMax(n1, n2 Node) Node {
    if v1, v1ok := n1.(*Value); v1ok {
        if v2, v2ok := n2.(*Value); v2ok {
            if v1.GreaterThan(v2) {
                return v1
            } else if v2.GreaterThan(v1) {
                return v2
            }
        }
    }
    if m1, m1ok := n1.(*OpMax); m1ok {
        if m2, m2ok := n2.(*OpMax); m2ok {
            m1.ns = append(m1.ns, m2.ns...)
        } else {
            m1.ns = append(m1.ns, n2)
        }
        return m1
    }
    if m2, m2ok := n2.(*OpMax); m2ok {
        m2.ns = append(m2.ns, n1)
        return m2
    }
    return &OpMax{ []Node{n1, n2} }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0