main.go

package main

import (
	"bufio"
	"flag"
	"fmt"
	"github.com/golang/glog"
	"io"
	"log"
	"os"
	"runtime"
	"runtime/pprof"
	"strconv"
	"sync"
)

type Input struct {
	k  int
	in [][]int
}
type Result int

func solve(input Input) Result {
	k := input.k
	for !input.isElegant(k) {
		k++
	}
	return Result(k*k - input.k*input.k)
}

func (in Input) isElegant(k int) bool {
	pat := createPattern(k, 1)
	for i := 0; i <= k-in.k; i++ {
	jl:
		for j := 0; j <= k-in.k; j++ {
			m := make(map[int]int)
			for r, rv := range in.in {
				for c, v := range rv {
					p := pat[i+r][j+c]
					if _, ex := m[p]; !ex {
						m[p] = v
					} else if m[p] != v {
						continue jl
					}
				}
			}
			return true
		}
	}
	return false
}

func createPattern(k, p int) [][]int {
	a := make([][]int, k)
	for i := range a {
		a[i] = make([]int, k)
	}
	if k == 1 {
		a[0][0] = p
		p++
		return a
	} else if k == 2 {
		a[0][0], a[1][1] = p, p
		p++
		a[0][1], a[1][0] = p, p
		p++
		return a
	}
	a[0][0], a[k-1][k-1] = p, p
	p++

	for r := 1; r < k; r++ {
		a[0][r], a[r][0] = p, p
		a[k-1][k-1-r], a[k-1-r][k-1] = p, p
		p++
	}
	b := createPattern(k - 2, p)
	for r := 0; r < len(b); r++ {
		for c, v := range b[r] {
			a[r+1][c+1] = v
		}
	}

	return a
}

func run(s *InOut) {
	glog.Infoln("input start")
	t := s.Next()
	inputs := make([]Input, t)
	for index := range inputs {
		k := s.Next()
		input := make([][]int, k)
		for i := range input {
			input[i] = make([]int, k)
		}
		for i := 0; i < k; i++ {
			for j := 0; j <= i; j++ {
				input[i-j][j] = s.Next()
			}
		}
		for i := k - 1; i > 0; i-- {
			for j := 0; j < i; j++ {
				input[k-j-1][k-i+j] = s.Next()
			}
		}
		inputs[index] = Input{
			k:  k,
			in: input,
		}
	}
	glog.Infoln("input end")

	glog.Infoln("solve start")
	loop(inputs, func(x Input) Result {
		result := solve(x)
		return result
	}, func(i int, r Result) {
		s.Println("Case #", i+1, ": ", r)
	})
	glog.Infoln("program end")
}

// Contest Template

func init() {
	runtime.GOMAXPROCS(runtime.NumCPU())
}

var cpuprofile = flag.String("cpuprofile", "", "write cpu profile to file")
var memprofile = flag.String("memprofile", "", "write memory profile to this file")

func main() {
	flag.Parse()
	if *cpuprofile != "" {
		f, err := os.Create(*cpuprofile)
		if err != nil {
			log.Fatal(err)
		}
		pprof.StartCPUProfile(f)
		defer pprof.StopCPUProfile()
	}
	s := NewInOut(os.Stdin, os.Stdout)
	run(s)
	s.Flush()
	if *memprofile != "" {
		f, err := os.Create(*memprofile)
		if err != nil {
			log.Fatal(err)
		}
		pprof.WriteHeapProfile(f)
		f.Close()
	}
}

// Pallarel
func loop(xs []Input, g func(Input) Result, h func(int, Result)) {
	ts := make([]Result, len(xs))
	var wg sync.WaitGroup
	for i, x := range xs {
		wg.Add(1)
		go func(i int, y Input) {
			ts[i] = g(y)
			wg.Done()
		}(i, x)
	}
	wg.Wait()
	for i, r := range ts {
		h(i, r)
	}
}

// InOut

type InOut struct {
	*bufio.Reader
	*bufio.Writer
}

func NewInOut(r io.Reader, w io.Writer) *InOut {
	return &InOut{bufio.NewReader(r), bufio.NewWriter(w)}
}

// Get Next Integer
func (s *InOut) Next() (r int) {
	b, _ := s.ReadByte()
	p := 1
	for (b < '0' || '9' < b) && b != '-' {
		b, _ = s.ReadByte()
	}
	if b == '-' {
		p = -1
		b, _ = s.ReadByte()
	}
	for '0' <= b && b <= '9' {
		r = 10*r + int(b-'0')
		b, _ = s.ReadByte()
	}
	return r * p
}

// Get Next int64
func (s *InOut) NextInt64() (r int64) {
	b, _ := s.ReadByte()
	p := int64(1)
	for (b < '0' || '9' < b) && b != '-' {
		b, _ = s.ReadByte()
	}
	if b == '-' {
		p = -1
		b, _ = s.ReadByte()
	}
	for '0' <= b && b <= '9' {
		r = 10*r + int64(b-'0')
		b, _ = s.ReadByte()
	}
	return r * p
}

// Get Next Line String
func (s *InOut) NextLine() (r string) {
	b, _ := s.ReadByte()
	for b == '\r' || b == '\n' {
		b, _ = s.ReadByte()
	}
	buf := make([]byte, 0)
	for ; b != '\r' && b != '\n'; b, _ = s.ReadByte() {
		buf = append(buf, b)
	}
	return string(buf)
}

// Get Next String using delimiter whitespace
func (s *InOut) NextStr() (r string) {
	return string(s.NextBytes())
}

// Get Next String using delimiter whitespace
func (s *InOut) NextBytes() (r []byte) {
	b, _ := s.ReadByte()
	for b == '\r' || b == '\n' || b == ' ' {
		b, _ = s.ReadByte()
	}
	buf := make([]byte, 0)
	for ; b != '\r' && b != '\n' && b != ' '; b, _ = s.ReadByte() {
		buf = append(buf, b)
	}
	return buf
}

// Print Strings using the suitable way to change type
func (s *InOut) Print(os ...interface{}) {
	for _, o := range os {
		switch o.(type) {
		case byte:
			s.WriteByte(o.(byte))
		case string:
			s.WriteString(o.(string))
		case int:
			s.WriteString(strconv.Itoa(o.(int)))
		case int64:
			s.WriteString(strconv.FormatInt(o.(int64), 10))
		default:
			s.WriteString(fmt.Sprint(o))
		}
	}
}

// Print Strings using the suitable way to change type with new line
func (s *InOut) Println(os ...interface{}) {
	for _, o := range os {
		s.Print(o)
	}
	s.Print("\n")
}

// Print immediately with new line (for debug)
func (s *InOut) PrintlnNow(o interface{}) {
	fmt.Println(o)
}

(pprof) top
Total: 8143 samples
    1925  23.6%  23.6%     4936  60.6% hash_insert
    1455  17.9%  41.5%     1964  24.1% evacuate
     943  11.6%  53.1%      943  11.6% runtime.aeshash64
     773   9.5%  62.6%     1043  12.8% runtime.mapaccess2_fast64
     386   4.7%  67.3%     6771  83.2% main.Input.isElegant
     299   3.7%  71.0%      299   3.7% scanblock
     220   2.7%  73.7%      220   2.7% sweepspan
     207   2.5%  76.2%      207   2.5% runtime.memcopy64
     202   2.5%  78.7%     5257  64.6% runtime.mapassign1
     164   2.0%  80.7%      164   2.0% runtime.memclr