← Home
For problem statement at 1000-1999/1600-1699/1610-1619/1616/problemE.txt this is a correct solution, but verifier at 1000-1999/1600-1699/1610-1619/1616/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"bytes"
	"io"
	"os"
	"strconv"
)

type FastScanner struct {
	data []byte
	idx  int
}

func (fs *FastScanner) skipSpaces() {
	for fs.idx < len(fs.data) && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
}

func (fs *FastScanner) nextInt() int {
	fs.skipSpaces()
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < len(fs.data) && fs.data[fs.idx] > ' ' {
		val = val*10 + int(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return val * sign
}

func (fs *FastScanner) nextString() string {
	fs.skipSpaces()
	start := fs.idx
	for fs.idx < len(fs.data) && fs.data[fs.idx] > ' ' {
		fs.idx++
	}
	return string(fs.data[start:fs.idx])
}

type Fenwick struct {
	bit []int
}

func NewFenwick(n int) *Fenwick {
	return &Fenwick{bit: make([]int, n+2)}
}

func (f *Fenwick) Add(i, v int) {
	for i < len(f.bit) {
		f.bit[i] += v
		i += i & -i
	}
}

func (f *Fenwick) Sum(i int) int {
	res := 0
	for i > 0 {
		res += f.bit[i]
		i -= i & -i
	}
	return res
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	fs := FastScanner{data: data}

	q := fs.nextInt()
	var out bytes.Buffer

	for ; q > 0; q-- {
		n := fs.nextInt()
		s := fs.nextString()
		t := fs.nextString()

		pos := make([][]int, 26)
		for i := 0; i < n; i++ {
			c := int(s[i] - 'a')
			pos[c] = append(pos[c], i+1)
		}

		ptr := make([]int, 26)
		fw := NewFenwick(n)

		const INF int64 = 1<<62 - 1
		ans := INF
		var cur int64

		for i := 0; i < n; i++ {
			tc := int(t[i] - 'a')

			for c := 0; c < tc; c++ {
				if ptr[c] < len(pos[c]) {
					p := pos[c][ptr[c]]
					moves := int64(p - 1 - fw.Sum(p))
					cand := cur + moves
					if cand < ans {
						ans = cand
					}
				}
			}

			if ptr[tc] == len(pos[tc]) {
				break
			}

			p := pos[tc][ptr[tc]]
			cur += int64(p - 1 - fw.Sum(p))
			fw.Add(p, 1)
			ptr[tc]++
		}

		if ans == INF {
			out.WriteString("-1\n")
		} else {
			out.WriteString(strconv.FormatInt(ans, 10))
			out.WriteByte('\n')
		}
	}

	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	w.Write(out.Bytes())
	w.Flush()
}