Submission #59181534


Source Code Expand

Copy
package main
import (
"bufio"
"fmt"
stdio "io"
"os"
"strconv"
)
var io *Iost
type Iost struct {
Scanner *bufio.Scanner
Writer *bufio.Writer
}
func NewIost(fp stdio.Reader, wfp stdio.Writer) *Iost {
const BufSize = 2000005
scanner := bufio.NewScanner(fp)
scanner.Split(bufio.ScanWords)
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
package main

import (
	"bufio"
	"fmt"
	stdio "io"
	"os"
	"strconv"
)

var io *Iost

type Iost struct {
	Scanner *bufio.Scanner
	Writer  *bufio.Writer
}

func NewIost(fp stdio.Reader, wfp stdio.Writer) *Iost {
	const BufSize = 2000005
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, BufSize), BufSize)
	return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)}
}
func (io *Iost) Text() string {
	if !io.Scanner.Scan() {
		panic("scan failed")
	}
	return io.Scanner.Text()
}
func (io *Iost) Atoi(s string) int                 { x, _ := strconv.Atoi(s); return x }
func (io *Iost) Atoi64(s string) int64             { x, _ := strconv.ParseInt(s, 10, 64); return x }
func (io *Iost) Atof64(s string) float64           { x, _ := strconv.ParseFloat(s, 64); return x }
func (io *Iost) NextInt() int                      { return io.Atoi(io.Text()) }
func (io *Iost) NextInt64() int64                  { return io.Atoi64(io.Text()) }
func (io *Iost) NextFloat64() float64              { return io.Atof64(io.Text()) }
func (io *Iost) Print(x ...interface{})            { fmt.Fprint(io.Writer, x...) }
func (io *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(io.Writer, s, x...) }
func (io *Iost) Println(x ...interface{})          { fmt.Fprintln(io.Writer, x...) }

const INF int = 1e18

type TrieNode struct {
	PreCount  int
	WordCount int
	MinLen    int
	Parent    *TrieNode
	Children  map[byte]*TrieNode
}

func NewTrieNode(parent *TrieNode) *TrieNode {
	return &TrieNode{
		MinLen:   INF,
		Parent:   parent,
		Children: make(map[byte]*TrieNode),
	}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{
		root: NewTrieNode(nil),
	}
}

func (t *Trie) Insert(s []byte) {
	if len(s) == 0 {
		return
	}
	root := t.root
	for i := 0; i < len(s); i++ {
		char := s[i]
		if _, ok := root.Children[char]; !ok {
			root.Children[char] = NewTrieNode(root)
		}
		root.Children[char].PreCount++
		root = root.Children[char]
		root.MinLen = min(root.MinLen, len(s))
	}
	root.WordCount++
}

func main() {
	in := os.Stdin
	out := os.Stdout
	io = NewIost(in, out)
	defer func() {
		io.Writer.Flush()
	}()

	N := io.NextInt()
	words := make([]string, N)
	for i := 0; i < N; i++ {
		words[i] = io.Text()
	}

	trie := NewTrie()

	query := func(s []byte) int {
		res := len(s)

		root := trie.root
		for i := 0; i < len(s); i++ {
			char := s[i]
			if _, ok := root.Children[char]; !ok {
				return res
			}
			root = root.Children[char]
			if root.PreCount > 0 {
				lcp := i + 1
				res = min(res, root.MinLen+len(s)-2*lcp)
			}
		}
		return res
	}

	for i := 0; i < N; i++ {
		io.Println(query([]byte(words[i])))
		trie.Insert([]byte(words[i]))
	}
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min32(a, b int32) int32 {
	if a < b {
		return a
	}
	return b
}

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

func mins(nums ...int) int {
	res := nums[0]
	for _, num := range nums {
		if num < res {
			res = num
		}
	}
	return res
}

func maxs(nums ...int) int {
	res := nums[0]
	for _, num := range nums {
		if num > res {
			res = num
		}
	}
	return res
}

Submission Info

Submission Time
Task G - Edit to Match
User caomeinaixi
Language Go (go 1.20.6)
Score 575
Code Size 3401 Byte
Status AC
Exec Time 63 ms
Memory 42100 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 575 / 575
Status
AC × 3
AC × 40
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 0 ms 1620 KB
00_sample_01.txt AC 0 ms 1604 KB
00_sample_02.txt AC 0 ms 1604 KB
01_random_00.txt AC 58 ms 41820 KB
01_random_01.txt AC 58 ms 41980 KB
01_random_02.txt AC 62 ms 41848 KB
01_random_03.txt AC 62 ms 41848 KB
01_random_04.txt AC 62 ms 41880 KB
01_random_05.txt AC 58 ms 42100 KB
01_random_06.txt AC 44 ms 5452 KB
01_random_07.txt AC 63 ms 41804 KB
01_random_08.txt AC 60 ms 41960 KB
01_random_09.txt AC 59 ms 41964 KB
01_random_10.txt AC 63 ms 42012 KB
01_random_11.txt AC 60 ms 41964 KB
01_random_12.txt AC 62 ms 41716 KB
01_random_13.txt AC 63 ms 41004 KB
01_random_14.txt AC 36 ms 13472 KB
01_random_15.txt AC 22 ms 3388 KB
01_random_16.txt AC 23 ms 3144 KB
01_random_17.txt AC 63 ms 41816 KB
01_random_18.txt AC 35 ms 22272 KB
01_random_19.txt AC 29 ms 15756 KB
01_random_20.txt AC 26 ms 12496 KB
01_random_21.txt AC 13 ms 2864 KB
01_random_22.txt AC 13 ms 2648 KB
01_random_23.txt AC 13 ms 2576 KB
01_random_24.txt AC 14 ms 2272 KB
01_random_25.txt AC 16 ms 2560 KB
01_random_26.txt AC 18 ms 2728 KB
01_random_27.txt AC 42 ms 5452 KB
01_random_28.txt AC 35 ms 4068 KB
01_random_29.txt AC 37 ms 5740 KB
01_random_30.txt AC 50 ms 12192 KB
01_random_31.txt AC 48 ms 18848 KB
01_random_32.txt AC 13 ms 2712 KB
01_random_33.txt AC 13 ms 2716 KB
01_random_34.txt AC 14 ms 2720 KB
01_random_35.txt AC 13 ms 2712 KB
01_random_36.txt AC 34 ms 5424 KB


2025-03-01 (Sat)
00:40:50 +00:00