← Home
For problem statement at 1000-1999/1400-1499/1470-1479/1474/problemD.txt this is a correct solution, but verifier at 1000-1999/1400-1499/1470-1479/1474/verifierD.go ends with OK can you fix the verifier? package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	fmt.Fscan(reader, &t)
	for i := 0; i < t; i++ {
		var n int
		fmt.Fscan(reader, &n)
		a := make([]int64, n+1)
		for j := 1; j <= n; j++ {
			fmt.Fscan(reader, &a[j])
		}

		P := make([]int64, n+1)
		first_neg := n + 1
		for j := 1; j <= n; j++ {
			P[j] = a[j] - P[j-1]
			if P[j] < 0 && first_neg == n+1 {
				first_neg = j
			}
		}

		if first_neg == n+1 && P[n] == 0 {
			fmt.Fprintln(writer, "YES")
			continue
		}

		minEven := make([]int64, n+2)
		minOdd := make([]int64, n+2)
		const INF int64 = 1e18
		minEven[n+1] = INF
		minOdd[n+1] = INF

		for j := n; j >= 1; j-- {
			minEven[j] = minEven[j+1]
			minOdd[j] = minOdd[j+1]
			if j%2 == 0 {
				if P[j] < minEven[j] {
					minEven[j] = P[j]
				}
			} else {
				if P[j] < minOdd[j] {
					minOdd[j] = P[j]
				}
			}
		}

		possible := false
		limit := first_neg
		if limit > n-1 {
			limit = n - 1
		}
		for k := 1; k <= limit; k++ {
			Pk_prime := a[k+1] - P[k-1]
			Pk1_prime := a[k] - a[k+1] + P[k-1]
			if Pk_prime < 0 || Pk1_prime < 0 {
				continue
			}
			Dk := 2 * (a[k] - a[k+1])

			var Pn_prime int64
			if (n-(k+1))%2 == 0 {
				Pn_prime = P[n] + Dk
			} else {
				Pn_prime = P[n] - Dk
			}

			if Pn_prime != 0 {
				continue
			}

			valid := true
			if (k+1)%2 == 0 {
				if minEven[k+1] != INF && minEven[k+1]+Dk < 0 {
					valid = false
				}
				if minOdd[k+1] != INF && minOdd[k+1]-Dk < 0 {
					valid = false
				}
			} else {
				if minOdd[k+1] != INF && minOdd[k+1]+Dk < 0 {
					valid = false
				}
				if minEven[k+1] != INF && minEven[k+1]-Dk < 0 {
					valid = false
				}
			}

			if valid {
				possible = true
				break
			}
		}

		if possible {
			fmt.Fprintln(writer, "YES")
		} else {
			fmt.Fprintln(writer, "NO")
		}
	}
}