For problem statement at 0-999/700-799/750-759/755/problemF.txt this is a correct solution, but verifier at 0-999/700-799/750-759/755/verifierF.go ends with All 100 tests passed can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
type BitSet []uint64
func NewBitSet(size int) BitSet {
return make(BitSet, (size+63)/64)
}
func (bs BitSet) Set(i int) {
bs[i/64] |= 1 << (i % 64)
}
func (bs BitSet) Get(i int) bool {
return (bs[i/64] & (1 << (i % 64))) != 0
}
func (bs BitSet) ShiftOr(shift int) {
wordShift := shift / 64
bitShift := uint(shift % 64)
if bitShift == 0 {
for i := len(bs) - 1; i >= wordShift; i-- {
bs[i] |= bs[i-wordShift]
}
} else {
invShift := 64 - bitShift
for i := len(bs) - 1; i >= wordShift; i-- {
v := bs[i-wordShift] << bitShift
if i-wordShift-1 >= 0 {
v |= bs[i-wordShift-1] >> invShift
}
bs[i] |= v
}
}
}
func readInt(reader *bufio.Reader) int {
var res int
for {
b, err := reader.ReadByte()
if err != nil {
return res
}
if b >= '0' && b <= '9' {
res = int(b - '0')
for {
b, err = reader.ReadByte()
if err != nil || b < '0' || b > '9' {
return res
}
res = res*10 + int(b-'0')
}
}
}
}
func main() {
reader := bufio.NewReader(os.Stdin)
n := readInt(reader)
if n == 0 {
return
}
k := readInt(reader)
p := make([]int, n+1)
for i := 1; i <= n; i++ {
p[i] = readInt(reader)
}
visited := make([]bool, n+1)
counts := make([]int, n+1)
for i := 1; i <= n; i++ {
if !visited[i] {
length := 0
curr := i
for !visited[curr] {
visited[curr] = true
curr = p[curr]
length++
}
counts[length]++
}
}
M := 0
for length, count := range counts {
M += (length / 2) * count
}
maxAns := 0
if k <= M {
maxAns = 2 * k
} else {
maxAns = M + k
}
if maxAns > n {
maxAns = n
}
minAns := 0
if k == 0 {
minAns = 0
} else {
dp := NewBitSet(k + 1)
dp.Set(0)
for length, count := range counts {
if length == 0 || count == 0 {
continue
}
c := count
power := 1
for c > 0 {
use := power
if c < power {
use = c
}
weight := length * use
if weight <= k {
dp.ShiftOr(weight)
}
c -= use
power *= 2
}
}
if dp.Get(k) {
minAns = k
} else {
minAns = k + 1
}
}
fmt.Printf("%d %d\n", minAns, maxAns)
}