結果
問題 | No.2102 [Cherry Alpha *] Conditional Reflection |
ユーザー | 草苺奶昔 |
提出日時 | 2023-12-16 16:54:44 |
言語 | Go (1.22.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,174 bytes |
コンパイル時間 | 11,845 ms |
コンパイル使用メモリ | 211,900 KB |
実行使用メモリ | 56,096 KB |
最終ジャッジ日時 | 2023-12-16 16:55:24 |
合計ジャッジ時間 | 37,364 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 217 ms
14,964 KB |
testcase_03 | AC | 285 ms
19,416 KB |
testcase_04 | AC | 222 ms
17,004 KB |
testcase_05 | AC | 158 ms
14,476 KB |
testcase_06 | AC | 228 ms
18,608 KB |
testcase_07 | AC | 284 ms
12,292 KB |
testcase_08 | AC | 55 ms
7,020 KB |
testcase_09 | AC | 271 ms
14,600 KB |
testcase_10 | AC | 100 ms
9,296 KB |
testcase_11 | AC | 96 ms
8,208 KB |
testcase_12 | AC | 178 ms
14,508 KB |
testcase_13 | AC | 314 ms
17,692 KB |
testcase_14 | AC | 186 ms
13,752 KB |
testcase_15 | AC | 280 ms
20,520 KB |
testcase_16 | AC | 361 ms
23,184 KB |
testcase_17 | AC | 183 ms
10,508 KB |
testcase_18 | AC | 294 ms
12,592 KB |
testcase_19 | AC | 138 ms
12,140 KB |
testcase_20 | AC | 349 ms
20,844 KB |
testcase_21 | AC | 102 ms
11,648 KB |
testcase_22 | AC | 406 ms
23,104 KB |
testcase_23 | AC | 406 ms
23,040 KB |
testcase_24 | AC | 405 ms
23,716 KB |
testcase_25 | AC | 406 ms
21,932 KB |
testcase_26 | AC | 408 ms
23,540 KB |
testcase_27 | AC | 424 ms
22,592 KB |
testcase_28 | AC | 405 ms
23,028 KB |
testcase_29 | AC | 408 ms
22,680 KB |
testcase_30 | AC | 417 ms
21,212 KB |
testcase_31 | AC | 406 ms
23,724 KB |
testcase_32 | AC | 410 ms
21,452 KB |
testcase_33 | AC | 428 ms
22,548 KB |
testcase_34 | AC | 406 ms
22,536 KB |
testcase_35 | AC | 395 ms
22,104 KB |
testcase_36 | AC | 436 ms
22,984 KB |
testcase_37 | AC | 421 ms
23,108 KB |
testcase_38 | AC | 394 ms
22,520 KB |
testcase_39 | AC | 421 ms
22,468 KB |
testcase_40 | AC | 412 ms
22,580 KB |
testcase_41 | AC | 410 ms
23,180 KB |
testcase_42 | AC | 373 ms
20,652 KB |
testcase_43 | AC | 396 ms
19,832 KB |
testcase_44 | AC | 377 ms
20,964 KB |
testcase_45 | AC | 374 ms
19,240 KB |
testcase_46 | AC | 378 ms
19,876 KB |
testcase_47 | AC | 320 ms
13,392 KB |
testcase_48 | AC | 321 ms
14,460 KB |
testcase_49 | AC | 328 ms
14,024 KB |
testcase_50 | AC | 339 ms
14,028 KB |
testcase_51 | AC | 314 ms
13,996 KB |
testcase_52 | AC | 253 ms
56,096 KB |
testcase_53 | AC | 254 ms
56,096 KB |
testcase_54 | AC | 254 ms
56,096 KB |
testcase_55 | AC | 245 ms
8,192 KB |
testcase_56 | AC | 242 ms
8,320 KB |
testcase_57 | AC | 243 ms
8,192 KB |
testcase_58 | AC | 253 ms
38,708 KB |
testcase_59 | AC | 426 ms
28,016 KB |
testcase_60 | AC | 92 ms
12,252 KB |
testcase_61 | AC | 244 ms
8,192 KB |
testcase_62 | AC | 12 ms
6,676 KB |
testcase_63 | WA | - |
testcase_64 | WA | - |
testcase_65 | WA | - |
testcase_66 | WA | - |
testcase_67 | AC | 327 ms
15,724 KB |
testcase_68 | WA | - |
testcase_69 | AC | 327 ms
16,640 KB |
ソースコード
package main import ( "bufio" "fmt" "os" ) // 顺序遍历每个单词,问之前是否见过类似的单词. // // `类似`: 最多交换一次相邻字符,可以得到相同的单词. // n<=2e5 sum(len(s))<=1e6 func ConditionalReflection(words []string) []bool { R := NewRollingHash(131, 47120526022187) res := make([]bool, len(words)) visited := make(map[int]struct{}) for i := 0; i < len(words); i++ { m := len(words[i]) word := words[i] table := R.Build(word) hashes := []int{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 int, mod int) int { if len(s) == 0 { return 0 } res := 0 for _, c := range s { res = (res*base + int(c)) % mod } return res } type RollingHash struct { base int mod int power []int } // 131/13331/1713302033171(回文素数) func NewRollingHash(base int, mod int) *RollingHash { return &RollingHash{ base: base, mod: mod, power: []int{1}, } } func (r *RollingHash) Build(s S) (hashTable []int) { sz := len(s) hashTable = make([]int, sz+1) for i, c := range s { hashTable[i+1] = (hashTable[i]*r.base + int(c)) % r.mod } return hashTable } func (r *RollingHash) Query(sTable []int, start, end int) int { 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 int, h2len int) int { r.expand(h2len) return (h1*r.power[h2len] + h2) % r.mod } func (r *RollingHash) AddChar(hash int, c int) int { return (hash*r.base + c) % r.mod } // 两个字符串的最长公共前缀长度. func (r *RollingHash) LCP(sTable []int, start1, end1 int, tTable []int, 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([]int, 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 }