GCJ/2008/1A/B/main.go

package main

import (
	"bufio"
	"container/list"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func leastMalted(scanner *bufio.Scanner) [][]int {
	caseCnt := ReadInt(scanner)
	answer := make([][]int, caseCnt)
	for i := 0; i < caseCnt; i++ {
		flavorCnt := ReadInt(scanner)
		custCnt := ReadInt(scanner)
		custList := list.New()
		singleList := list.New()
		ansMap := make(map[int]int)
		for j := 0; j < custCnt; j++ { // Read all customers => List
			custInts := ReadInts(scanner)
			cust := list.New()
			for k := 1; k < 2*custInts[0]; k += 2 {
				cust.PushBack(Pair{custInts[k], custInts[k+1]})
			}
			if cust.Len() == 1 {
				singleList.PushBack(cust)
			} else {
				custList.PushBack(cust)
			}
		}
		validCase := true
		for validCase && singleList.Len() != 0 {
			for curr := singleList.Front(); curr != nil; {
				cust := curr.Value.(*list.List)
				p := cust.Front().Value.(Pair)
				if v, ok := ansMap[p._1]; ok && v != p._2 {
					// If conflict with ansMap, go to next case
					validCase = false
					break
				}
				ansMap[p._1] = p._2 // Else, put into ansMap
				next := curr.Next()
				singleList.Remove(curr)
				curr = next
			}
			for curr := custList.Front(); validCase && curr != nil; {
				cust := curr.Value.(*list.List)
				skipCust := false // If customer is already satisfied, skip
				for p := cust.Front(); p != nil; {
					pair := p.Value.(Pair)
					if v, ok := ansMap[pair._1]; ok {
						if v != pair._2 {
							// Next pair
							next := p.Next()
							cust.Remove(p)
							p = next
							continue
						}
						// Satisfied, skip
						skipCust = true
						break
					}
					p = p.Next()
				}
				if skipCust {
					next := curr.Next()
					custList.Remove(curr)
					curr = next
					continue
				}
				if cust.Len() == 1 { // Move to singleList
					singleList.PushBack(cust)
					next := curr.Next()
					custList.Remove(curr)
					curr = next
				} else if cust.Len() == 0 { // No candidate, wrong case
					validCase = false
				} else { // Next cust
					curr = curr.Next()
				}
			}
		}
		if validCase {
			answer[i] = make([]int, flavorCnt)
			for k, v := range ansMap {
				answer[i][k-1] = v
			}
		}
	}
	return answer
}

func main() {
	inputFiles := []string{"B-small-practice.in", "B-large-practice.in", "test.in"}
	outputFiles := []string{"result-small.out", "result-large.out", "test.out"}
	const (
		small = iota
		large
		test
	)

	fileType := test

	fin, _ := os.Open(inputFiles[fileType])
	defer fin.Close()

	scanner := bufio.NewScanner(fin)
	answer := leastMalted(scanner)

	fout, _ := os.Create(outputFiles[fileType])
	defer fout.Close()

	for i, nums := range answer {
		var ans string
		if len(nums) == 0 {
			ans = "IMPOSSIBLE"
		} else {
			strs := make([]string, len(nums))
			for j, n := range nums {
				strs[j] = strconv.Itoa(n)
			}
			ans = strings.Join(strs, " ")
		}
		s := fmt.Sprintf("Case #%d: %s\n", i+1, ans)
		fout.WriteString(s)
	}
}