← Home
For problem statement at 0-999/500-599/510-519/510/problemE.txt this is a correct solution, but verifier at 0-999/500-599/510-519/510/verifierE.go ends with All tests passed! can you fix the verifier? package main

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

type Edge struct {
	to, rev, cap, flow int
}

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

	var n int
	if _, err := fmt.Fscan(in, &n); err != nil {
		return
	}

	a := make([]int, n+1)
	evens := []int{}
	odds := []int{}
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &a[i])
		if a[i]%2 == 0 {
			evens = append(evens, i)
		} else {
			odds = append(odds, i)
		}
	}

	if len(evens) != len(odds) {
		fmt.Fprintln(out, "Impossible")
		return
	}

	isPrime := make([]bool, 20005)
	for i := 2; i < 20005; i++ {
		isPrime[i] = true
	}
	for i := 2; i*i < 20005; i++ {
		if isPrime[i] {
			for j := i * i; j < 20005; j += i {
				isPrime[j] = false
			}
		}
	}

	S := 0
	T := n + 1
	graph := make([][]Edge, n+2)

	addEdge := func(u, v, cap int) {
		graph[u] = append(graph[u], Edge{v, len(graph[v]), cap, 0})
		graph[v] = append(graph[v], Edge{u, len(graph[u]) - 1, 0, 0})
	}

	for _, i := range evens {
		addEdge(S, i, 2)
		for _, j := range odds {
			if isPrime[a[i]+a[j]] {
				addEdge(i, j, 1)
			}
		}
	}
	for _, j := range odds {
		addEdge(j, T, 2)
	}

	level := make([]int, n+2)
	var bfs func() bool
	bfs = func() bool {
		for i := 0; i <= n+1; i++ {
			level[i] = -1
		}
		level[S] = 0
		q := []int{S}
		for len(q) > 0 {
			u := q[0]
			q = q[1:]
			for _, e := range graph[u] {
				if e.flow < e.cap && level[e.to] == -1 {
					level[e.to] = level[u] + 1
					q = append(q, e.to)
				}
			}
		}
		return level[T] != -1
	}

	var dfs func(u, pushed int, ptr []int) int
	dfs = func(u, pushed int, ptr []int) int {
		if pushed == 0 || u == T {
			return pushed
		}
		for ; ptr[u] < len(graph[u]); ptr[u]++ {
			e := &graph[u][ptr[u]]
			tr := e.to
			if level[u]+1 != level[tr] || e.cap-e.flow == 0 {
				continue
			}
			push := pushed
			if e.cap-e.flow < push {
				push = e.cap - e.flow
			}
			p := dfs(tr, push, ptr)
			if p == 0 {
				continue
			}
			e.flow += p
			graph[tr][e.rev].flow -= p
			return p
		}
		return 0
	}

	flow := 0
	for bfs() {
		ptr := make([]int, n+2)
		for {
			pushed := dfs(S, 1000000, ptr)
			if pushed == 0 {
				break
			}
			flow += pushed
		}
	}

	if flow != n {
		fmt.Fprintln(out, "Impossible")
		return
	}

	adj := make([][]int, n+1)
	for _, i := range evens {
		for _, e := range graph[i] {
			if e.cap == 1 && e.flow == 1 {
				adj[i] = append(adj[i], e.to)
				adj[e.to] = append(adj[e.to], i)
			}
		}
	}

	visited := make([]bool, n+1)
	var tables [][]int
	for i := 1; i <= n; i++ {
		if !visited[i] {
			var table []int
			curr := i
			prev := -1
			for !visited[curr] {
				visited[curr] = true
				table = append(table, curr)
				next := adj[curr][0]
				if next == prev {
					next = adj[curr][1]
				}
				prev = curr
				curr = next
			}
			tables = append(tables, table)
		}
	}

	fmt.Fprintln(out, len(tables))
	for _, table := range tables {
		fmt.Fprint(out, len(table))
		for _, idx := range table {
			fmt.Fprint(out, " ", idx)
		}
		fmt.Fprintln(out)
	}
}