← Home
For problem statement at 1000-1999/1200-1299/1240-1249/1242/problemC.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1240-1249/1242/verifierC.go ends with All tests passed can you fix the verifier? package main

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

type CycleEdge struct {
	fromBox int
	val     int64
	toBox   int
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 1024*1024*10)
	scanner.Buffer(buf, 1024*1024*10)

	scanInt := func() int {
		scanner.Scan()
		res, _ := strconv.Atoi(scanner.Text())
		return res
	}

	scanInt64 := func() int64 {
		scanner.Scan()
		res, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		return res
	}

	if !scanner.Scan() {
		return
	}
	k, _ := strconv.Atoi(scanner.Text())

	boxes := make([][]int64, k)
	S := make([]int64, k)
	var totalSum int64
	valToBox := make(map[int64]int)

	for i := 0; i < k; i++ {
		ni := scanInt()
		boxes[i] = make([]int64, ni)
		for j := 0; j < ni; j++ {
			v := scanInt64()
			boxes[i][j] = v
			S[i] += v
			totalSum += v
			valToBox[v] = i
		}
	}

	if totalSum%int64(k) != 0 {
		fmt.Println("No")
		return
	}

	T := totalSum / int64(k)

	has_cycle := make([]bool, 1<<k)
	cycle_info := make([][]CycleEdge, 1<<k)

	for b := 0; b < k; b++ {
		for _, x := range boxes[b] {
			curr := x
			mask := 0
			var edges []CycleEdge

			valid := false
			for {
				curr_b := valToBox[curr]
				if (mask & (1 << curr_b)) != 0 {
					if curr == x {
						valid = true
					}
					break
				}
				mask |= (1 << curr_b)
				nextVal := T - S[curr_b] + curr
				next_b, exists := valToBox[nextVal]
				if !exists {
					break
				}
				edges = append(edges, CycleEdge{
					fromBox: next_b,
					val:     nextVal,
					toBox:   curr_b,
				})
				curr = nextVal
			}
			if valid {
				if !has_cycle[mask] {
					has_cycle[mask] = true
					cycle_info[mask] = edges
				}
			}
		}
	}

	dp := make([]bool, 1<<k)
	from_mask := make([]int, 1<<k)
	dp[0] = true

	for m := 0; m < (1<<k); m++ {
		if !dp[m] {
			continue
		}
		comp := ((1 << k) - 1) ^ m
		for sub := comp; sub > 0; sub = (sub - 1) & comp {
			if has_cycle[sub] {
				next_m := m | sub
				if !dp[next_m] {
					dp[next_m] = true
					from_mask[next_m] = sub
				}
			}
		}
	}

	if !dp[(1<<k)-1] {
		fmt.Println("No")
	} else {
		fmt.Println("Yes")
		ansC := make([]int64, k)
		ansP := make([]int, k)
		curr_m := (1 << k) - 1
		for curr_m > 0 {
			sub := from_mask[curr_m]
			for _, edge := range cycle_info[sub] {
				ansC[edge.fromBox] = edge.val
				ansP[edge.fromBox] = edge.toBox + 1
			}
			curr_m ^= sub
		}
		for i := 0; i < k; i++ {
			fmt.Println(ansC[i], ansP[i])
		}
	}
}