← Home
For problem statement at 0-999/300-399/330-339/339/problemE.txt this is a correct solution, but verifier at 0-999/300-399/330-339/339/verifierE.go ends with All 100 tests passed can you fix the verifier? package main

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

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func reverseArr(A []int, l, r int) {
	for i, j := l, r; i < j; i, j = i+1, j-1 {
		A[i], A[j] = A[j], A[i]
	}
}

func getBreaks(A []int) []int {
	var B []int
	for i := 0; i < len(A)-1; i++ {
		if abs(A[i]-A[i+1]) != 1 {
			B = append(B, i)
		}
	}
	return B
}

func solve(A []int, depth int) [][2]int {
	B := getBreaks(A)
	if len(B) == 0 {
		return [][2]int{}
	}
	if depth == 0 {
		return nil
	}
	if len(B) > 2*depth {
		return nil
	}

	reqCL := len(B) - 2*depth + 4
	if reqCL < 1 {
		reqCL = 1
	}

	n := len(A) - 2
	isBreak := make([]bool, n+2)
	for _, b := range B {
		isBreak[b] = true
	}

	cands := make(map[[2]int]bool)

	for _, b := range B {
		l := b + 1
		if l >= 1 && l <= n {
			for r := l; r <= n; r++ {
				cands[[2]int{l, r}] = true
			}
		}
		r := b
		if r >= 1 && r <= n {
			for l := 1; l <= r; l++ {
				cands[[2]int{l, r}] = true
			}
		}
	}

	if reqCL <= 2 {
		pos := make([]int, n+2)
		for i, v := range A {
			pos[v] = i
		}

		for l := 1; l <= n; l++ {
			v := A[l-1]
			if v-1 >= 0 {
				r := pos[v-1]
				if r >= l && r <= n {
					cands[[2]int{l, r}] = true
				}
			}
			if v+1 <= n+1 {
				r := pos[v+1]
				if r >= l && r <= n {
					cands[[2]int{l, r}] = true
				}
			}
		}
		for r := 1; r <= n; r++ {
			v := A[r+1]
			if v-1 >= 0 {
				l := pos[v-1]
				if l >= 1 && l <= r {
					cands[[2]int{l, r}] = true
				}
			}
			if v+1 <= n+1 {
				l := pos[v+1]
				if l >= 1 && l <= r {
					cands[[2]int{l, r}] = true
				}
			}
		}
	}

	type Cand struct {
		l, r, cl int
	}
	var validCands []Cand

	for c := range cands {
		l, r := c[0], c[1]
		if l == r {
			continue
		}

		L := 0
		if isBreak[l-1] {
			L++
		}
		if isBreak[r] {
			L++
		}

		C := 0
		if abs(A[l-1]-A[r]) == 1 {
			C++
		}
		if abs(A[l]-A[r+1]) == 1 {
			C++
		}

		cl := C + L
		if cl >= reqCL {
			validCands = append(validCands, Cand{l, r, cl})
		}
	}

	sort.Slice(validCands, func(i, j int) bool {
		return validCands[i].cl > validCands[j].cl
	})

	for _, cand := range validCands {
		l, r := cand.l, cand.r
		reverseArr(A, l, r)
		res := solve(A, depth-1)
		if res != nil {
			return append(res, [2]int{l, r})
		}
		reverseArr(A, l, r)
	}

	return nil
}

func main() {
	buf := make([]byte, 8192)
	var pos, length int
	in := os.Stdin

	nextByte := func() byte {
		if pos >= length {
			n, err := in.Read(buf)
			if n == 0 || err != nil {
				return 0
			}
			pos = 0
			length = n
		}
		b := buf[pos]
		pos++
		return b
	}

	nextInt := func() int {
		b := nextByte()
		for b <= ' ' && b != 0 {
			b = nextByte()
		}
		if b == 0 {
			return 0
		}
		res := 0
		for b > ' ' {
			res = res*10 + int(b-'0')
			b = nextByte()
		}
		return res
	}

	n := nextInt()
	if n == 0 {
		return
	}

	A := make([]int, n+2)
	A[0] = 0
	A[n+1] = n + 1
	for i := 1; i <= n; i++ {
		A[i] = nextInt()
	}

	for depth := 0; depth <= 3; depth++ {
		ans := solve(A, depth)
		if ans != nil {
			fmt.Println(len(ans))
			for _, move := range ans {
				fmt.Printf("%d %d\n", move[0], move[1])
			}
			return
		}
	}
}