結果

問題 No.2102 [Cherry Alpha *] Conditional Reflection
ユーザー 草苺奶昔
提出日時 2023-12-16 16:40:54
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 3,271 bytes
コンパイル時間 13,720 ms
コンパイル使用メモリ 233,516 KB
実行使用メモリ 59,492 KB
最終ジャッジ日時 2024-09-27 07:41:26
合計ジャッジ時間 40,809 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 28 WA * 42
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
    "bufio"
    "fmt"
    "os"
)
// 顺序遍历每个单词,问之前是否见过类似的单词.
//
//  `类似`: 最多交换一次相邻字符,可以得到相同的单词.
//  n<=2e5 sum(len(s))<=1e6
func ConditionalReflection(words []string) []bool {
    R := NewRollingHash(13331, 1000000007)
    res := make([]bool, len(words))
    visited := make(map[int64]struct{})
    for i := 0; i < len(words); i++ {
        m := len(words[i])
        word := words[i]
        table := R.Build(word)
        hashes := []int64{R.Query(table, 0, m)} // 不交换
        for j := 0; j < m-1; j++ {              // 交换
            newWord := string(word[j+1]) + string(word[j])
            mid := R.Query(R.Build(newWord), 0, 2)
            left := R.Query(table, 0, j)
            right := R.Query(table, j+2, m)
            left = R.Combine(left, mid, 2)
            left = R.Combine(left, right, m-j-2)
            hashes = append(hashes, left)
        }
        for _, h := range hashes {
            if _, ok := visited[h]; ok {
                res[i] = true
                break
            }
        }
        visited[hashes[0]] = struct{}{}
    }
    return res
}
func main() {
    // https://yukicoder.me/problems/no/2102
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()
    var n int
    fmt.Fscan(in, &n)
    words := make([]string, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &words[i])
    }
    res := ConditionalReflection(words)
    for i := 0; i < n; i++ {
        if res[i] {
            fmt.Fprintln(out, "Yes")
        } else {
            fmt.Fprintln(out, "No")
        }
    }
}
type S = string
func GetHash(s S, base int64, mod int64) int64 {
    if len(s) == 0 {
        return 0
    }
    res := int64(0)
    for i := 0; i < len(s); i++ {
        res = (res*base + int64(s[i])) % mod
    }
    return res
}
type RollingHash struct {
    base  int64
    mod   int64
    power []int64
}
// 131/13331/1713302033171(回文素数)
func NewRollingHash(base int64, mod int64) *RollingHash {
    return &RollingHash{
        base:  base,
        mod:   mod,
        power: []int64{1},
    }
}
func (r *RollingHash) Build(s S) (hashTable []int64) {
    sz := len(s)
    hashTable = make([]int64, sz+1)
    for i := 0; i < sz; i++ {
        hashTable[i+1] = (hashTable[i]*r.base%r.mod + int64(s[i])) % r.mod
    }
    return hashTable
}
func (r *RollingHash) Query(sTable []int64, start, end int) int64 {
    r.expand(end - start)
    res := (sTable[end] - sTable[start]*r.power[end-start]%r.mod)
    if res < 0 {
        res += r.mod
    }
    return res
}
func (r *RollingHash) Combine(h1, h2 int64, h2len int) int64 {
    r.expand(h2len)
    return (h1*r.power[h2len]%r.mod + h2) % r.mod
}
func (r *RollingHash) AddChar(hash int64, c byte) int64 {
    return (hash*r.base%r.mod + int64(c)) % r.mod
}
// 两个字符串的最长公共前缀长度.
func (r *RollingHash) LCP(sTable []int64, start1, end1 int, tTable []int64, start2, end2 int) int {
    len1 := end1 - start1
    len2 := end2 - start2
    len := min(len1, len2)
    low := 0
    high := len + 1
    for high-low > 1 {
        mid := (low + high) / 2
        if r.Query(sTable, start1, start1+mid) == r.Query(tTable, start2, start2+mid) {
            low = mid
        } else {
            high = mid
        }
    }
    return low
}
func (r *RollingHash) expand(sz int) {
    if len(r.power) < sz+1 {
        preSz := len(r.power)
        r.power = append(r.power, make([]int64, sz+1-preSz)...)
        for i := preSz - 1; i < sz; i++ {
            r.power[i+1] = (r.power[i] * r.base) % r.mod
        }
    }
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0