For problem statement at 0-999/100-199/170-179/178/problemC1.txt this is a correct solution, but verifier at 0-999/100-199/170-179/178/verifierC1.go ends with all tests passed can you fix the verifier? package main
import (
"fmt"
"io"
"os"
)
type FastScanner struct {
data []byte
idx int
}
func NewFastScanner() *FastScanner {
b, _ := io.ReadAll(os.Stdin)
return &FastScanner{data: b}
}
func (fs *FastScanner) nextChar() byte {
n := len(fs.data)
for fs.idx < n && fs.data[fs.idx] <= ' ' {
fs.idx++
}
if fs.idx >= n {
return 0
}
ch := fs.data[fs.idx]
fs.idx++
return ch
}
func (fs *FastScanner) nextInt() int {
n := len(fs.data)
for fs.idx < n {
c := fs.data[fs.idx]
if c >= '0' && c <= '9' {
break
}
fs.idx++
}
val := 0
for fs.idx < n {
c := fs.data[fs.idx]
if c < '0' || c > '9' {
break
}
val = val*10 + int(c-'0')
fs.idx++
}
return val
}
type Fenwick struct {
n int
bit []int
mask int
}
func NewFenwickAllOnes(n int) *Fenwick {
bit := make([]int, n+1)
for i := 1; i <= n; i++ {
bit[i] = 1
}
for i := 1; i <= n; i++ {
j := i + (i & -i)
if j <= n {
bit[j] += bit[i]
}
}
mask := 1
for mask < n {
mask <<= 1
}
return &Fenwick{n: n, bit: bit, mask: mask}
}
func (f *Fenwick) add(pos, delta int) {
for i := pos + 1; i <= f.n; i += i & -i {
f.bit[i] += delta
}
}
func (f *Fenwick) sum(pos int) int {
if pos < 0 {
return 0
}
res := 0
for i := pos + 1; i > 0; i -= i & -i {
res += f.bit[i]
}
return res
}
func (f *Fenwick) rangeSum(l, r int) int {
if l > r {
return 0
}
return f.sum(r) - f.sum(l-1)
}
func (f *Fenwick) lowerBound(target int) int {
idx := 0
for step := f.mask; step != 0; step >>= 1 {
next := idx + step
if next <= f.n && f.bit[next] < target {
idx = next
target -= f.bit[next]
}
}
return idx
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
func main() {
fs := NewFastScanner()
h := fs.nextInt()
m := fs.nextInt()
n := fs.nextInt()
g := gcd(h, m)
l := h / g
cellToPos := make([]int, h)
for r := 0; r < g; r++ {
x := r
start := r * l
for j := 0; j < l; j++ {
cellToPos[x] = start + j
x += m
if x >= h {
x -= h
}
}
}
fw := NewFenwickAllOnes(h)
idPos := make(map[int]int, n)
var ans int64
for i := 0; i < n; i++ {
op := fs.nextChar()
if op == '+' {
id := fs.nextInt()
hash := fs.nextInt()
p := cellToPos[hash]
start := (p / l) * l
end := start + l - 1
var q int
if fw.rangeSum(p, end) > 0 {
q = fw.lowerBound(fw.sum(p-1) + 1)
} else {
q = fw.lowerBound(fw.sum(start-1) + 1)
}
dist := q - p
if dist < 0 {
dist += l
}
ans += int64(dist)
fw.add(q, -1)
idPos[id] = q
} else {
id := fs.nextInt()
p := idPos[id]
fw.add(p, 1)
delete(idPos, id)
}
}
fmt.Print(ans)
}