For problem statement at 1000-1999/1700-1799/1730-1739/1730/problemF.txt this is a correct solution, but verifier at 1000-1999/1700-1799/1730-1739/1730/verifierF.go ends with case 1 failed: expected 0 got 1
input:
2 2
2 1
exit status 1 can you fix the verifier? ```go
package main
import (
"bufio"
"fmt"
"os"
)
type FastScanner struct {
r *bufio.Reader
}
func NewFastScanner() *FastScanner {
return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}
func (fs *FastScanner) NextInt() int {
sign := 1
val := 0
c, _ := fs.r.ReadByte()
for (c < '0' || c > '9') && c != '-' {
c, _ = fs.r.ReadByte()
}
if c == '-' {
sign = -1
c, _ = fs.r.ReadByte()
}
for c >= '0' && c <= '9' {
val = val*10 + int(c-'0')
c, _ = fs.r.ReadByte()
}
return sign * val
}
type BIT struct {
n int
data []int
}
func NewBIT(n int) *BIT {
return &BIT{n: n, data: make([]int, n+2)}
}
func (b *BIT) Add(i, v int) {
for i <= b.n {
b.data[i] += v
i += i & -i
}
}
func (b *BIT) Sum(i int) int {
s := 0
for i > 0 {
s += b.data[i]
i -= i & -i
}
return s
}
func main() {
fs := NewFastScanner()
n := fs.NextInt()
k := fs.NextInt()
p := make([]int, n+1)
for i := 1; i <= n; i++ {
p[i] = fs.NextInt()
}
posOfVal := make([]int, n+1)
for i := 1; i <= n; i++ {
posOfVal[p[i]] = i
}
S := make([]int, n)
for v := 1; v <= n; v++ {
S[v-1] = posOfVal[v]
}
size := 1
if k > 0 {
size = 1 << uint(k)
}
const INF int64 = 1<<60
dpStart := make([]int64, size)
dpNext := make([]int64, size)
dpInter := make([]int64, size)
for i := 0; i < size; i++ {
dpStart[i] = INF
}
dpStart[0] = 0
// popcount for masks up to 2^k
popc := make([]int, size)
for m := 1; m < size; m++ {
popc[m] = popc[m>>1] + (m & 1)
}
bit := NewBIT(n)
// temp arrays per ptr
gpast := make([]int, k+1)
gtMask := make([]int, k+1)
for ptr := 0; ptr < n; ptr++ {
m := k
if rem := n-1-ptr; rem < m {
m = rem
}
validMask := 0
if m > 0 {
validMask = (1 << uint(m)) - 1
}
tMax := k
if rem := n-1-ptr; rem < tMax {
tMax = rem
}
for t := 0; t <= tMax; t++ {
x := S[ptr+t]
gpast[t] = ptr - bit.Sum(x)
}
for t := 0; t <= tMax; t++ {
mask := 0
for u := 1; u <= m; u++ {
if S[ptr+u] > S[ptr+t] {
mask |= 1 << uint(u-1)
}
}
gtMask[t] = mask
}
for i := 0; i < size; i++ {
if (i & ^validMask) != 0 {
dpInter[i] = INF
} else {
dpInter[i] = dpStart[i]
}
dpNext[i] = INF
}
for pc := 0; pc <= m; pc++ {
for mask := 0; mask < size; mask++ {
if (mask&^validMask) != 0 || dpInter[mask] == INF || popc[mask] != pc {
continue
}
for t := 1; t <= m; t++ {
if (mask>>uint(t-1))&1 == 0 {
add := int64(gpast[t] + popc[mask>Mask[t]])
nm := mask | (1 << uint(t-1))
if v := dpInter[mask] + add; v < dpInter[nm] {
dpInter[nm] = v
}
}
}
}
}
for mask := 0; mask < size; mask++ {
if (mask&^validMask) != 0 || dpInter[mask] == INF {
continue
}
add0 := int64(gpast[0] + popc[mask>Mask[0]])
nm := mask >> 1
if v := dpInter[mask] + add0; v < dpNext[nm] {
dpNext[nm] = v
}
}
copy(dpStart, dpNext)
bit.Add(S[ptr], 1)
}
fmt.Println(dpStart[0])
}
```