// http://www.spoj.com/problems/HOMO/ package main import ( "bufio" "io" "os" "runtime/pprof" "strconv" "strings" ) type List struct { Data []int Map map[int]int } func (l *List) Insert(n int) { l.Data = append(l.Data, n) l.Map[n]++ } func (l *List) Delete(n int) { for i, v := range l.Data { if v == n { l.Data = append(l.Data[:i], l.Data[i+1:]...) switch l.Map[n] { case 1: delete(l.Map, n) default: l.Map[n]-- } return } } } func (l List) IsHomo() bool { var top int for _, v := range l.Map { if v > top { top = v } } return top > 1 } func (l List) IsHetero() bool { return len(l.Map) > 1 } func Split(s string) (string, int) { i := strings.Index(s, " ") n, _ := strconv.Atoi(s[i+1:]) return s[:i], n } func (l List) String() string { homo, hetero := l.IsHomo(), l.IsHetero() switch { case homo && hetero: return "both" case hetero: return "hetero" case homo: return "homo" default: return "neither" } } func Homo(r io.Reader, w io.Writer) { scanner := bufio.NewScanner(r) scanner.Scan() n, _ := strconv.Atoi(scanner.Text()) l := List{ Data: make([]int, 0, n), Map: make(map[int]int), } for scanner.Scan() { s, n := Split(scanner.Text()) switch s { case "insert": l.Insert(n) case "delete": l.Delete(n) } io.WriteString(w, l.String()) io.WriteString(w, "\n") } } func main() { f, _ := os.Create("cpu.out") pprof.StartCPUProfile(f) defer pprof.StopCPUProfile() Homo(os.Stdin, os.Stdout) }