← Home
For problem statement at 0-999/900-999/900-909/909/problemF.txt this is a correct solution, but verifier at 0-999/900-999/900-909/909/verifierF.go ends with All 100 tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func buildP(n int) (bool, []int) {
	if n%2 == 1 {
		return false, nil
	}
	p := make([]int, n+1)
	cur := n
	for cur > 0 {
		k := bits.Len(uint(cur)) - 1
		low := 1 << uint(k)
		mask := (1 << uint(k+1)) - 1
		for x := low; x <= cur; x++ {
			y := mask ^ x
			if y == 0 {
				return false, nil
			}
			p[x] = y
			p[y] = x
		}
		cur = (mask ^ cur) - 1
	}
	return true, p[1:]
}

func isPow2(n int) bool {
	return n > 0 && (n&(n-1)) == 0
}

func buildQ(n int) (bool, []int) {
	if n == 1 || n == 2 || n == 3 || n == 5 || isPow2(n) {
		if n == 6 {
			// special handled below
		} else {
			return false, nil
		}
	}
	q := make([]int, n+1)
	if n == 6 {
		q[1] = 5
		q[2] = 3
		q[3] = 1
		q[4] = 6
		q[5] = 4
		q[6] = 2
		return true, q[1:]
	}
	for k := 1; (1<<uint(k)) <= n; k++ {
		L := 1 << uint(k)
		R := (1 << uint(k+1)) - 1
		if R > n {
			R = n
		}
		if L > R {
			continue
		}
		if k == 2 {
			evens := []int{}
			odds := []int{}
			for i := L; i <= R; i++ {
				if i%2 == 0 {
					evens = append(evens, i)
				} else {
					odds = append(odds, i)
				}
			}
			if len(evens) >= 2 {
				for i := 0; i < len(evens); i++ {
					q[evens[i]] = evens[(i+1)%len(evens)]
				}
			} else if len(evens) == 1 {
				return false, nil
			}
			if len(odds) >= 2 {
				for i := 0; i < len(odds); i++ {
					q[odds[i]] = odds[(i+1)%len(odds)]
				}
			} else {
				return false, nil
			}
		} else {
			for i := L; i < R; i++ {
				q[i] = i + 1
			}
			q[R] = L
		}
	}
	c := 5
	d := q[c]
	q[c] = 1
	q[1] = d
	return true, q[1:]
}

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
	}

	okP, p := buildP(n)
	if !okP {
		fmt.Fprintln(out, "NO")
	} else {
		fmt.Fprintln(out, "YES")
		for i := 0; i < n; i++ {
			if i > 0 {
				fmt.Fprint(out, " ")
			}
			fmt.Fprint(out, p[i])
		}
		fmt.Fprintln(out)
	}

	okQ, q := buildQ(n)
	if !okQ {
		fmt.Fprintln(out, "NO")
	} else {
		fmt.Fprintln(out, "YES")
		for i := 0; i < n; i++ {
			if i > 0 {
				fmt.Fprint(out, " ")
			}
			fmt.Fprint(out, q[i])
		}
		fmt.Fprintln(out)
	}
}