← Home
For problem statement at 1000-1999/1200-1299/1210-1219/1210/problemE.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1210-1219/1210/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, k int
	fmt.Fscan(in, &n, &k)

	p := make([]int, k)
	for i := 0; i < k; i++ {
		p[i] = i
	}

	var perms [][]int
	idMap := make(map[int]int)

	encode := func(p []int) int {
		res := 0
		for _, v := range p {
			res = res*5 + v
		}
		return res
	}

	for {
		tmp := make([]int, k)
		copy(tmp, p)
		idMap[encode(tmp)] = len(perms)
		perms = append(perms, tmp)

		i := k - 2
		for i >= 0 && p[i] >= p[i+1] {
			i--
		}
		if i < 0 {
			break
		}
		j := k - 1
		for p[j] <= p[i] {
			j--
		}
		p[i], p[j] = p[j], p[i]
		for left, right := i+1, k-1; left < right; left, right = left+1, right-1 {
			p[left], p[right] = p[right], p[left]
		}
	}

	V := len(perms)
	comp := make([][]int, V)
	for i := 0; i < V; i++ {
		comp[i] = make([]int, V)
		for j := 0; j < V; j++ {
			tmp := make([]int, k)
			for x := 0; x < k; x++ {
				tmp[x] = perms[i][perms[j][x]]
			}
			comp[i][j] = idMap[encode(tmp)]
		}
	}

	type Subgroup struct {
		mask [2]uint64
	}

	addElement := func(sub Subgroup, x int) Subgroup {
		if (sub.mask[x/64] & (1 << (x % 64))) != 0 {
			return sub
		}
		var q []int
		var cur []int
		for i := 0; i < V; i++ {
			if (sub.mask[i/64] & (1 << (i % 64))) != 0 {
				cur = append(cur, i)
			}
		}
		q = append(q, x)
		sub.mask[x/64] |= (1 << (x % 64))
		cur = append(cur, x)

		for head := 0; head < len(q); head++ {
			u := q[head]
			nCur := len(cur)
			for i := 0; i < nCur; i++ {
				v := cur[i]
				
				w1 := comp[u][v]
				if (sub.mask[w1/64] & (1 << (w1 % 64))) == 0 {
					sub.mask[w1/64] |= (1 << (w1 % 64))
					q = append(q, w1)
					cur = append(cur, w1)
				}
				
				w2 := comp[v][u]
				if (sub.mask[w2/64] & (1 << (w2 % 64))) == 0 {
					sub.mask[w2/64] |= (1 << (w2 % 64))
					q = append(q, w2)
					cur = append(cur, w2)
				}
			}
		}
		return sub
	}

	var idSub Subgroup
	idSub.mask[0] = 1

	type Entry struct {
		sub Subgroup
		l   int
	}

	var entries []Entry
	var total int64

	for r := 1; r <= n; r++ {
		tmp := make([]int, k)
		for i := 0; i < k; i++ {
			fmt.Fscan(in, &tmp[i])
			tmp[i]--
		}
		x := idMap[encode(tmp)]

		var newEntries []Entry
		for _, e := range entries {
			e.sub = addElement(e.sub, x)
			if len(newEntries) > 0 && newEntries[len(newEntries)-1].sub == e.sub {
				
			} else {
				newEntries = append(newEntries, e)
			}
		}

		subR := addElement(idSub, x)
		if len(newEntries) > 0 && newEntries[len(newEntries)-1].sub == subR {
			
		} else {
			newEntries = append(newEntries, Entry{sub: subR, l: r})
		}
		entries = newEntries

		for i := 0; i < len(entries); i++ {
			nextL := r + 1
			if i+1 < len(entries) {
				nextL = entries[i+1].l
			}
			cnt := int64(nextL - entries[i].l)
			size := int64(bits.OnesCount64(entries[i].sub.mask[0]) + bits.OnesCount64(entries[i].sub.mask[1]))
			total += size * cnt
		}
	}

	fmt.Println(total)
}