← Home
For problem statement at 1000-1999/1900-1999/1940-1949/1945/problemH.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1940-1949/1945/verifierH.go ends with case 1 failed: expected YES
2 10 20 
4 11 27 35 45 got YES
2 20 10
4 45 27 35 11
input:
1
6 4
45 27 35 20 10 11
exit status 1 can you fix the verifier? ```go
package main

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

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func solve() {
	var n, x int
	fmt.Fscan(reader, &n, &x)
	a := make([]int, n)
	maxVal := 0
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &a[i])
		if a[i] > maxVal {
			maxVal = a[i]
		}
	}

	pos := make([][]int, maxVal+1)
	for i, v := range a {
		pos[v] = append(pos[v], i)
	}

	tree := make([]int, 2*n)
	for i := 0; i < 2*n; i++ {
		tree[i] = -1
	}
	for i := 0; i < n; i++ {
		tree[n+i] = a[i]
	}
	for i := n - 1; i > 0; i-- {
		tree[i] = tree[2*i] & tree[2*i+1]
	}

	query := func(l, r int) int {
		res := -1
		for l < r {
			if l&1 == 1 {
				res &= tree[l]
				l++
			}
			if r&1 == 1 {
				r--
				res &= tree[r]
			}
			l >>= 1
			r >>= 1
		}
		return res
	}

	gAll := a[0]
	for i := 1; i < n; i++ {
		gAll = gcd(gAll, a[i])
	}

	indices := make([]int, 0, n)

	for g := maxVal; g > x; g-- {
		indices = indices[:0]
		for k := 1; k*g <= maxVal; k++ {
			if len(pos[k*g]) > 0 {
				indices = append(indices, pos[k*g]...)
			}
		}

		cnt := len(indices)
		if cnt < 2 {
			continue
		}

		sort.Ints(indices)
		rem := n - cnt

		if rem >= 2 {
			andVal := -1
			curr := 0
			for _, idx := range indices {
				if curr < idx {
					andVal &= query(curr, idx)
				}
				curr = idx + 1
			}
			if curr < n {
				andVal &= query(curr, n)
			}
			
			if g > andVal+x {
				printYes(a, indices, nil)
				return
			}
		} else if rem == 1 {
			missing := -1
			curr := 0
			for _, idx := range indices {
				if idx != curr {
					missing = curr
					break
				}
				curr++
			}
			if missing == -1 {
				missing = n - 1
			}
			
			y := a[missing]
			for _, zIdx := range indices {
				if g > (y&a[zIdx])+x {
					blue := []int{missing, zIdx}
					red := make([]int, 0, n-2)
					for _, v := range indices {
						if v != zIdx {
							red = append(red, v)
						}
					}
					fmt.Fprintln(writer, "YES")
					fmt.Fprint(writer, len(red))
					for _, v := range red {
						fmt.Fprint(writer, " ", a[v])
					}
					fmt.Fprintln(writer)
					fmt.Fprint(writer, len(blue))
					for _, v := range blue {
						fmt.Fprint(writer, " ", a[v])
					}
					fmt.Fprintln(writer)
					return
				}
			}
		} else {
			if g == gAll {
				allAnd := query(0, n)
				if g <= allAnd+x {
					continue 
				}
				
				pref := make([]int, n)
				suff := make([]int, n)
				pref[0] = a[0]
				for i := 1; i < n; i++ {
					pref[i] = pref[i-1] & a[i]
				}
				suff[n-1] = a[n-1]
				for i := n - 2; i >= 0; i-- {
					suff[i] = suff[i+1] & a[i]
				}
				
				getAndExcl := func(u, v int) int {
					if u > v { u, v = v, u }
					res := -1
					if u > 0 { res &= pref[u-1] }
					if u+1 < v { 
						res &= query(u+1, v)
					}
					if v < n-1 { res &= suff[v+1] }
					return res
				}
				
				found := false
				var u, v int
				
				limit := 60
				if n < limit { limit = n }
				for i := 0; i < limit; i++ {
					for j := i + 1; j < limit; j++ {
						val := getAndExcl(i, j)
						if g > val+x {
							u, v = i, j
							found = true
							goto DONE
						}
					}
				}
				
				if !found {
					for i := 0; i < limit; i++ {
						idx1 := n - 1 - i
						if idx1 < 0 { break }
						for j := i + 1; j < limit; j++ {
							idx2 := n - 1 - j
							if idx2 < 0 || idx2 >= idx1 { continue }
							val := getAndExcl(idx2, idx1)
							if g > val+x {
								u, v = idx2, idx1
								found = true
								goto DONE
							}
						}
					}
				}

			DONE:
				if found {
					blue := []int{u, v}
					red := make([]int, 0, n-2)
					for i := 0; i < n; i++ {
						if i != u && i != v {
							red = append(red, i)
						}
					}
					fmt.Fprintln(writer, "YES")
					fmt.Fprint(writer, len(red))
					for _, val := range red {
						fmt.Fprint(writer, " ", a[val])
					}
					fmt.Fprintln(writer)
					fmt.Fprint(writer, len(blue))
					for _, val := range blue {
						fmt.Fprint(writer, " ", a[val])
					}
					fmt.Fprintln(writer)
					return
				}
			}
		}
	}

	fmt.Fprintln(writer, "NO")
}

func printYes(a []int, redIndices []int, blueIndices []int) {
	mask := make([]bool, len(a))
	for _, idx := range redIndices {
		mask[idx] = true
	}
	
	fmt.Fprintln(writer, "YES")
	fmt.Fprint(writer, len(redIndices))
	for _, idx := range redIndices {
		fmt.Fprint(writer, " ", a[idx])
	}
	fmt.Fprintln(writer)
	
	countBlue := 0
	if blueIndices != nil {
		countBlue = len(blueIndices)
	} else {
		countBlue = len(a) - len(redIndices)
	}
	fmt.Fprint(writer, countBlue)
	
	if blueIndices != nil {
		for _, idx := range blueIndices {
			fmt.Fprint(writer, " ", a[idx])
		}
	} else {
		for i, v := range a {
			if !mask[i] {
				fmt.Fprint(writer, " ", v)
			}
		}
	}
	fmt.Fprintln(writer)
}

var reader *bufio.Reader
var writer *bufio.Writer

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++ {
		solve()
	}
}
```