結果

問題 No.1439 Let's Compare!!!!
コンテスト
ユーザー ID 21712
提出日時 2026-05-25 16:31:51
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 190 ms / 2,000 ms
コード長 2,586 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,138 ms
コンパイル使用メモリ 288,512 KB
実行使用メモリ 14,720 KB
最終ジャッジ日時 2026-05-25 21:41:09
合計ジャッジ時間 17,187 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"
import "container/heap"

func main() {
	rd:=bf.NewReader(Stdin)
	wr:=bf.NewWriter(Stdout)
	defer wr.Flush()
	
	var n int
	Fscan(rd,&n)
	
	var s,t string
	Fscan(rd,&s,&t)
	
	bS := []byte(s)
	bT := []byte(t)

	pq := make(PQ, 0, n)
	
	items := make([]*Item, n)

	for i := 0; i < n; i++ {
		item := newItem(i)
		items[i] = item
		if bS[i] != bT[i] {
			heap.Push(&pq, item)
		}
	}
	
	var q int
	Fscan(rd,&q)
	
	for ; q > 0 ; q-- {
		var c string
		var x, y int
		Fscan(rd,&c,&x,&y)
		x--
		y += '0'
		switch c {
			case "S":
				bS[x] = byte(y)
			case "T":
				bT[x] = byte(y)
		}
		if bS[x] == bT[x] {
			if items[x].index >= 0 {
				heap.Remove(&pq, items[x].index)
				items[x].index = -1
			}
		} else {
			if items[x].index < 0 {
				heap.Push(&pq, items[x])
			}
		}
		if pq.Len() == 0 {
			Fprintln(wr, "=")
		} else {
			pos := pq.Peek().value
			switch {
				case bS[pos] > bT[pos]:
					Fprintln(wr, ">")
				case bS[pos] < bT[pos]:
					Fprintln(wr, "<")
			}
		}
	}
}


type Item struct {
	index, value int
}

func newItem(value int) *Item {
	return &Item{ index: -1, value: value }
}

type PQ []*Item

func (pq PQ) Peek() *Item { 
	if pq.Len() > 0 {
		return pq[0]
	} else {
		return nil
	}
}
func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].value < pq[j].value }
func (pq PQ) Swap(i, j int) {
	pq[i],pq[j] = pq[j],pq[i]
	pq[i].index = i
	pq[j].index = j
}
func (pq *PQ) Push(v any) {
	item := v.(*Item)
	item.index = len(*pq)
	*pq = append(*pq, item)
}
func (pq *PQ) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1
	old[n-1] = nil
	*pq = old[:n-1]
	return item
}

/*
考察

書き換えて毎度数値まるごと比較では間に合わない

2つの数値S,Tの各桁のうち数字が異なる桁でもっとも上位の桁を素早く見つけて答えるが必要
SとTで数字が異なる桁をピックアップして
桁の位置をキーとして順序付きセット(平衡二分探索木など)に入れて管理すればよさそう？
クエリの書き換えで桁が一致したらセットからキーを削除
クエリの書き換えで桁が異なったらセットにキーを挿入
セットの最小のキーである桁の位置の比較で大小判定はできる
セットが空になった場合はSとTは同値にとなる

問題は…Go言語には順序付きセットも順序付きマップも標準ライブラリには無い…

まぁ、今回の問題はcontainer/heapでも代用できるとは思う…
*/
0