For problem statement at 1000-1999/1400-1499/1440-1449/1444/problemD.txt this is a correct solution, but verifier at 1000-1999/1400-1499/1440-1449/1444/verifierD.go ends with wrong answer on test 72
input:
3
4
3 1 2 2
4
1 2 4 5
4
2 4 2 1
3
1 3 4
4
2 3 3 2
4
2 1 3 4
expected:Yes
0 5
2 5
2 6
4 6
4 2
3 2
3 0
0 0
No
Yes
0 4
2 4
2 5
5 5
5 2
3 2
3 0
0 0
got:Yes
0 0
1 0
1 2
4 2
4 6
2 6
2 5
0 5
No
Yes
0 0
2 0
2 2
5 2
5 5
2 5
2 4
0 4
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"math/rand"
"os"
"sort"
)
type Point struct {
x int
y int
}
type Segment struct {
x1, y1 int
x2, y2 int
h bool
minx int
maxx int
miny int
maxy int
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func sortedCopy(a []int, asc bool) []int {
b := append([]int(nil), a...)
sort.Ints(b)
if !asc {
for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
b[i], b[j] = b[j], b[i]
}
}
return b
}
func shuffledCopy(a []int, rng *rand.Rand) []int {
b := append([]int(nil), a...)
rng.Shuffle(len(b), func(i, j int) {
b[i], b[j] = b[j], b[i]
})
return b
}
func partition(arr []int) (bool, []int, []int) {
total := 0
for _, v := range arr {
total += v
}
if total%2 != 0 {
return false, nil, nil
}
half := total / 2
parent := make([]int, half+1)
for i := 1; i <= half; i++ {
parent[i] = -1
}
parent[0] = -2
for i, v := range arr {
for s := half; s >= v; s-- {
if parent[s] == -1 && parent[s-v] != -1 {
parent[s] = i
}
}
}
if parent[half] == -1 {
return false, nil, nil
}
chosen := make([]bool, len(arr))
s := half
for s > 0 {
i := parent[s]
if i < 0 {
return false, nil, nil
}
chosen[i] = true
s -= arr[i]
}
var a, b []int
for i, v := range arr {
if chosen[i] {
a = append(a, v)
} else {
b = append(b, v)
}
}
return true, a, b
}
func build(startH bool, hp []int, hn []int, vp []int, vn []int) ([]Point, bool) {
hs := make([]int, 0, len(hp)+len(hn))
hs = append(hs, hp...)
hs = append(hs, hn...)
vs := make([]int, 0, len(vp)+len(vn))
vs = append(vs, vp...)
vs = append(vs, vn...)
n := len(hs)
if len(vs) != n {
return nil, false
}
x, y := 0, 0
pts := make([]Point, 0, 2*n+1)
pts = append(pts, Point{0, 0})
if startH {
for i := 0; i < n; i++ {
if i < len(hp) {
x += hs[i]
} else {
x -= hs[i]
}
pts = append(pts, Point{x, y})
if i < len(vp) {
y += vs[i]
} else {
y -= vs[i]
}
pts = append(pts, Point{x, y})
}
} else {
for i := 0; i < n; i++ {
if i < len(vp) {
y += vs[i]
} else {
y -= vs[i]
}
pts = append(pts, Point{x, y})
if i < len(hp) {
x += hs[i]
} else {
x -= hs[i]
}
pts = append(pts, Point{x, y})
}
}
if x != 0 || y != 0 {
return nil, false
}
return pts[:2*n], true
}
func isEndpoint(s Segment, x, y int) bool {
return (s.x1 == x && s.y1 == y) || (s.x2 == x && s.y2 == y)
}
func badIntersection(a, b Segment) bool {
if a.h && b.h {
if a.y1 != b.y1 {
return false
}
l := max(a.minx, b.minx)
r := min(a.maxx, b.maxx)
if l > r {
return false
}
if l < r {
return true
}
return !(isEndpoint(a, l, a.y1) && isEndpoint(b, l, b.y1))
}
if !a.h && !b.h {
if a.x1 != b.x1 {
return false
}
l := max(a.miny, b.miny)
r := min(a.maxy, b.maxy)
if l > r {
return false
}
if l < r {
return true
}
return !(isEndpoint(a, a.x1, l) && isEndpoint(b, b.x1, l))
}
var h, v Segment
if a.h {
h, v = a, b
} else {
h, v = b, a
}
x := v.x1
y := h.y1
if x < h.minx || x > h.maxx || y < v.miny || y > v.maxy {
return false
}
return !(isEndpoint(h, x, y) && isEndpoint(v, x, y))
}
func validate(pts []Point) bool {
m := len(pts)
if m < 4 {
return false
}
segs := make([]Segment, m)
for i := 0; i < m; i++ {
a := pts[i]
b := pts[(i+1)%m]
if a.x == b.x && a.y == b.y {
return false
}
if a.x != b.x && a.y != b.y {
return false
}
h := a.y == b.y
segs[i] = Segment{
x1: a.x,
y1: a.y,
x2: b.x,
y2: b.y,
h: h,
minx: min(a.x, b.x),
maxx: max(a.x, b.x),
miny: min(a.y, b.y),
maxy: max(a.y, b.y),
}
}
for i := 0; i < m; i++ {
if segs[i].h == segs[(i+1)%m].h {
return false
}
}
for i := 0; i < m; i++ {
for j := i + 1; j < m; j++ {
if j == i+1 || (i == 0 && j == m-1) {
continue
}
if badIntersection(segs[i], segs[j]) {
return false
}
}
}
return true
}
func attempt(startH bool, posH, negH, posV, negV []int, hPosAsc, hNegAsc, vPosAsc, vNegAsc bool) ([]Point, bool) {
hp := sortedCopy(posH, hPosAsc)
hn := sortedCopy(negH, hNegAsc)
vp := sortedCopy(posV, vPosAsc)
vn := sortedCopy(negV, vNegAsc)
pts, ok := build(startH, hp, hn, vp, vn)
if !ok {
return nil, false
}
if !validate(pts) {
return nil, false
}
return pts, true
}
func attemptRandom(startH bool, posH, negH, posV, negV []int, rng *rand.Rand) ([]Point, bool) {
hp := shuffledCopy(posH, rng)
hn := shuffledCopy(negH, rng)
vp := shuffledCopy(posV, rng)
vn := shuffledCopy(negV, rng)
pts, ok := build(startH, hp, hn, vp, vn)
if !ok {
return nil, false
}
if !validate(pts) {
return nil, false
}
return pts, true
}
func solve(ha, hb, va, vb []int, caseIdx int) ([]Point, bool) {
type groups struct {
posH []int
negH []int
posV []int
negV []int
}
var gs []groups
gs = append(gs, groups{ha, hb, va, vb})
gs = append(gs, groups{hb, ha, va, vb})
gs = append(gs, groups{ha, hb, vb, va})
gs = append(gs, groups{hb, ha, vb, va})
for _, g := range gs {
preferredStartH := len(g.posH) <= len(g.posV)
if pts, ok := attempt(preferredStartH, g.posH, g.negH, g.posV, g.negV, true, false, true, true); ok {
return pts, true
}
if pts, ok := attempt(!preferredStartH, g.posH, g.negH, g.posV, g.negV, true, false, true, true); ok {
return pts, true
}
}
for _, g := range gs {
preferredStartH := len(g.posH) <= len(g.posV)
starts := []bool{preferredStartH, !preferredStartH}
for _, startH := range starts {
for _, hPosAsc := range []bool{true, false} {
for _, hNegAsc := range []bool{false, true} {
for _, vPosAsc := range []bool{true, false} {
for _, vNegAsc := range []bool{true, false} {
if pts, ok := attempt(startH, g.posH, g.negH, g.posV, g.negV, hPosAsc, hNegAsc, vPosAsc, vNegAsc); ok {
return pts, true
}
}
}
}
}
}
}
rng := rand.New(rand.NewSource(int64(caseIdx + 1)))
for _, g := range gs {
preferredStartH := len(g.posH) <= len(g.posV)
starts := []bool{preferredStartH, !preferredStartH}
for _, startH := range starts {
for t := 0; t < 80; t++ {
if pts, ok := attemptRandom(startH, g.posH, g.negH, g.posV, g.negV, rng); ok {
return pts, true
}
}
}
}
return nil, false
}
func main() {
in := bufio.NewReaderSize(os.Stdin, 1<<20)
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
var t int
fmt.Fscan(in, &t)
for tc := 0; tc < t; tc++ {
var h int
fmt.Fscan(in, &h)
hs := make([]int, h)
for i := 0; i < h; i++ {
fmt.Fscan(in, &hs[i])
}
var v int
fmt.Fscan(in, &v)
vs := make([]int, v)
for i := 0; i < v; i++ {
fmt.Fscan(in, &vs[i])
}
if h != v {
fmt.Fprintln(out, "No")
continue
}
okH, ha, hb := partition(hs)
if !okH {
fmt.Fprintln(out, "No")
continue
}
okV, va, vb := partition(vs)
if !okV {
fmt.Fprintln(out, "No")
continue
}
pts, ok := solve(ha, hb, va, vb, tc)
if !ok {
fmt.Fprintln(out, "No")
continue
}
fmt.Fprintln(out, "Yes")
for _, p := range pts {
fmt.Fprintln(out, p.x, p.y)
}
}
}