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]
}
}