← Home
For problem statement at 1000-1999/1500-1599/1500-1509/1503/problemD.txt this is a correct solution, but verifier at 1000-1999/1500-1599/1500-1509/1503/verifierD.go ends with case 3 failed: expected 1 got -1

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var scanner = bufio.NewScanner(os.Stdin)

func init() {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)
}

func nextInt() int {
	scanner.Scan()
	res := 0
	for _, b := range scanner.Bytes() {
		res = res*10 + int(b-'0')
	}
	return res
}

type Card struct {
	x, y       int
	orig_state int
}

func main() {
	if !scanner.Scan() {
		return
	}
	res := 0
	for _, b := range scanner.Bytes() {
		res = res*10 + int(b-'0')
	}
	n := res

	if n == 0 {
		return
	}

	cards := make([]Card, n)
	for i := 0; i < n; i++ {
		u := nextInt()
		v := nextInt()
		x, y := u, v
		orig := 0
		if u > v {
			x, y = v, u
			orig = 1
		}
		cards[i] = Card{x, y, orig}
	}

	sort.Slice(cards, func(i, j int) bool {
		return cards[i].x < cards[j].x
	})

	for i := 0; i < n; i++ {
		if cards[i].x != i+1 {
			fmt.Println("-1")
			return
		}
	}

	y := make([]int, n)
	for i := 0; i < n; i++ {
		y[i] = cards[i].y
	}

	P_min := make([]int, n)
	P_min[0] = y[0]
	for i := 1; i < n; i++ {
		if y[i] < P_min[i-1] {
			P_min[i] = y[i]
		} else {
			P_min[i] = P_min[i-1]
		}
	}

	S_max := make([]int, n)
	S_max[n-1] = y[n-1]
	for i := n - 2; i >= 0; i-- {
		if y[i] > S_max[i+1] {
			S_max[i] = y[i]
		} else {
			S_max[i] = S_max[i+1]
		}
	}

	splits := make([]bool, n)
	for i := 0; i < n-1; i++ {
		if P_min[i] > S_max[i+1] {
			splits[i] = true
		}
	}

	totalFlips := 0
	start := 0
	for i := 0; i < n; i++ {
		if i == n-1 || splits[i] {
			end := i
			v0 := 1000000000
			v1 := 1000000000
			costSame := 0
			costDiff := 0

			for j := start; j <= end; j++ {
				val := y[j]
				color := -1
				if val < v0 && val < v1 {
					if v0 < v1 {
						v0 = val
						color = 0
					} else {
						v1 = val
						color = 1
					}
				} else if val < v0 {
					v0 = val
					color = 0
				} else if val < v1 {
					v1 = val
					color = 1
				} else {
					fmt.Println("-1")
					return
				}

				if color == cards[j].orig_state {
					costSame++
				} else {
					costDiff++
				}
			}

			if costSame < costDiff {
				totalFlips += costSame
			} else {
				totalFlips += costDiff
			}

			start = i + 1
		}
	}

	fmt.Println(totalFlips)
}