← Home
For problem statement at 1000-1999/1700-1799/1780-1789/1787/problemF.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1780-1789/1787/verifierF.go ends with case 31 failed: expected YES
1 3 2 got YES
2 1 3
input:
1
3 1
1 2 3
exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
)

func readInt(reader *bufio.Reader) int {
	var n int
	var c byte
	var err error
	for {
		c, err = reader.ReadByte()
		if err != nil {
			return n
		}
		if c >= '0' && c <= '9' {
			break
		}
	}
	n = int(c - '0')
	for {
		c, err = reader.ReadByte()
		if err != nil || c < '0' || c > '9' {
			break
		}
		n = n*10 + int(c-'0')
	}
	return n
}

func main() {
	reader := bufio.NewReaderSize(os.Stdin, 1<<16)
	writer := bufio.NewWriterSize(os.Stdout, 1<<16)
	defer writer.Flush()

	t := readInt(reader)

	for tc := 0; tc < t; tc++ {
		n := readInt(reader)
		k := readInt(reader)

		a := make([]int, n+1)
		for i := 1; i <= n; i++ {
			a[i] = readInt(reader)
		}

		visited := make([]bool, n+1)
		cyclesByLen := make(map[int][][]int)

		for i := 1; i <= n; i++ {
			if !visited[i] {
				cycle := []int{}
				curr := i
				for !visited[curr] {
					visited[curr] = true
					cycle = append(cycle, curr)
					curr = a[curr]
				}
				cyclesByLen[len(cycle)] = append(cyclesByLen[len(cycle)], cycle)
			}
		}

		ans := make([]int, n+1)
		req := 0
		if k < 30 {
			req = 1 << k
		} else {
			req = n + 1
		}

		possible := true

		for Lprime, list := range cyclesByLen {
			count := len(list)
			if Lprime%2 == 0 {
				if count%req != 0 {
					possible = false
					break
				}
				for i := 0; i < count; i += req {
					chunk := list[i : i+req]
					processChunk(chunk, Lprime, req, k, ans)
				}
			} else {
				idx := 0
				if req <= count {
					numReq := count / req
					for i := 0; i < numReq; i++ {
						chunk := list[idx : idx+req]
						processChunk(chunk, Lprime, req, k, ans)
						idx += req
					}
				}
				rem := count % req
				for c := 0; c < 30; c++ {
					if (rem & (1 << c)) != 0 {
						chunk := list[idx : idx+(1<<c)]
						processChunk(chunk, Lprime, 1<<c, k, ans)
						idx += (1 << c)
					}
				}
			}
		}

		if !possible {
			fmt.Fprintln(writer, "NO")
		} else {
			fmt.Fprintln(writer, "YES")
			for i := 1; i <= n; i++ {
				if i > 1 {
					fmt.Fprint(writer, " ")
				}
				fmt.Fprint(writer, ans[i])
			}
			fmt.Fprintln(writer)
		}
	}
}

func powMod(base, exp, mod int) int {
	if mod == 1 {
		return 0
	}
	res := 1
	base = base % mod
	for exp > 0 {
		if exp%2 == 1 {
			res = (res * base) % mod
		}
		base = (base * base) % mod
		exp /= 2
	}
	return res
}

func processChunk(chunk [][]int, Lprime, m, k int, ans []int) {
	L := Lprime * m
	C := make([]int, L)
	step := powMod(2, k, L)

	for j := 0; j < m; j++ {
		for x := 0; x < Lprime; x++ {
			idx := (j + x*step) % L
			C[idx] = chunk[j][x]
		}
	}

	for i := 0; i < L; i++ {
		ans[C[i]] = C[(i+1)%L]
	}
}