103.go

// UVa 103 - Stacking Boxes

package main

import (
	"fmt"
	"io"
	"os"
	"sort"
	"strconv"
	"strings"
)

func fit(a, b []int) bool {
	for i := range a {
		if a[i] >= b[i] {
			return false
		}
	}
	return true
}

func lis(n int, boxes [][]int) []int {
	sort.Slice(boxes, func(i, j int) bool {
		for idx := range boxes[i] {
			if boxes[i][idx] != boxes[j][idx] {
				return boxes[i][idx] < boxes[j][idx]
			}
		}
		return false
	})
	length := make([]int, n)
	for i := range length {
		length[i] = 1
	}
	pre := make([]int, n)
	for i := range pre {
		pre[i] = -1
	}
	max, maxIdx := 0, 0
	for i := 0; i < n-1; i++ {
		for j := i + 1; j < n; j++ {
			if fit(boxes[i], boxes[j]) {
				if length[i]+1 > length[j] {
					if length[j] = length[i] + 1; length[j] > max {
						max = length[j]
						maxIdx = j
					}
					pre[j] = i
				}
			}
		}
	}

	ret := []int{maxIdx}
	for pre[maxIdx] != -1 {
		maxIdx = pre[maxIdx]
		ret = append([]int{maxIdx}, ret...)
	}
	return ret
}

func isSame(a, b []int) bool {
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func output(out io.Writer, order []int, box, original [][]int) {
	var ret []string
	for _, v := range order {
		for j := range original {
			if isSame(box[v], original[j]) {
				ret = append(ret, strconv.Itoa(j+1))
				break
			}
		}
	}
	fmt.Fprintln(out, len(ret))
	fmt.Fprintln(out, strings.Join(ret, " "))
}

func main() {
	in, _ := os.Open("103.in")
	defer in.Close()
	out, _ := os.Create("103.out")
	defer out.Close()

	var n, d int
	for {
		if _, err := fmt.Fscanf(in, "%d%d", &n, &d); err != nil {
			break
		}
		boxes := make([][]int, n)
		for i := range boxes {
			boxes[i] = make([]int, d)
			for j := range boxes[i] {
				fmt.Fscanf(in, "%d", &boxes[i][j])
			}
			sort.Ints(boxes[i])
		}
		original := make([][]int, n)
		copy(original, boxes)
		output(out, lis(n, boxes), boxes, original)
	}
}