summaryrefslogtreecommitdiff
path: root/main.go
diff options
context:
space:
mode:
Diffstat (limited to 'main.go')
-rw-r--r--main.go101
1 files changed, 101 insertions, 0 deletions
diff --git a/main.go b/main.go
new file mode 100644
index 0000000..bfbdc7c
--- /dev/null
+++ b/main.go
@@ -0,0 +1,101 @@
+// 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)
+}