← Home
For problem statement at 1000-1999/1900-1999/1900-1909/1901/problemF.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1900-1909/1901/verifierF.go ends with failed to build reference: exit status 1
stat /tmp/go-build1804800797/b001/exe/1901F.go: directory not found

exit status 1 can you fix the verifier? package main

import (
	"bytes"
	"io"
	"math"
	"os"
	"strconv"
)

type Point struct {
	x int64
	y int64
}

func cross(a, b, c Point) int64 {
	return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x)
}

func buildHull(l, r int, h []int64) []Point {
	hull := make([]Point, 0, r-l+1)
	for i := l; i <= r; i++ {
		p := Point{int64(i), h[i]}
		for len(hull) >= 2 && cross(hull[len(hull)-2], hull[len(hull)-1], p) >= 0 {
			hull = hull[:len(hull)-1]
		}
		hull = append(hull, p)
	}
	return hull
}

func pairValue(lx, ly, rx, ry, n int64) float64 {
	u := n - 1 - 2*lx
	v := 2*rx - (n - 1)
	num := 2.0 * (float64(v)*float64(ly) + float64(u)*float64(ry))
	den := float64(u + v)
	return num / den
}

func queryToRight(hull []Point, x, y, n int64) float64 {
	if len(hull) == 1 {
		return pairValue(x, y, hull[0].x, hull[0].y, n)
	}
	q := Point{x, y}
	lo, hi := 0, len(hull)-2
	ans := -1
	for lo <= hi {
		mid := (lo + hi) >> 1
		if cross(q, hull[mid], hull[mid+1]) >= 0 {
			ans = mid
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	idx := 0
	if ans != -1 {
		idx = ans + 1
	}
	p := hull[idx]
	return pairValue(x, y, p.x, p.y, n)
}

func queryToLeft(hull []Point, x, y, n int64) float64 {
	if len(hull) == 1 {
		return pairValue(hull[0].x, hull[0].y, x, y, n)
	}
	q := Point{x, y}
	lo, hi := 0, len(hull)-2
	idx := len(hull) - 1
	for lo <= hi {
		mid := (lo + hi) >> 1
		if cross(q, hull[mid], hull[mid+1]) >= 0 {
			idx = mid
			hi = mid - 1
		} else {
			lo = mid + 1
		}
	}
	p := hull[idx]
	return pairValue(p.x, p.y, x, y, n)
}

func maxf(a, b float64) float64 {
	if a > b {
		return a
	}
	return b
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	ptr := 0
	nextInt := func() int64 {
		for ptr < len(data) && (data[ptr] < '0' || data[ptr] > '9') {
			ptr++
		}
		var v int64
		for ptr < len(data) && data[ptr] >= '0' && data[ptr] <= '9' {
			v = v*10 + int64(data[ptr]-'0')
			ptr++
		}
		return v
	}

	n := int(nextInt())
	a := make([]int64, n)
	b := make([]int64, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt()
	}
	for i := 0; i < n; i++ {
		b[i] = nextInt()
	}

	ans := make([]float64, n)
	N := int64(n)
	negInf := math.Inf(-1)

	if n%2 == 0 {
		leftCnt := n / 2
		leftEnd := leftCnt - 1
		rightStart := leftCnt

		rightHullA := buildHull(rightStart, n-1, a)
		leftValA := make([]float64, leftCnt)
		leftValB := make([]float64, leftCnt)
		for i := 0; i < leftCnt; i++ {
			x := int64(i)
			leftValA[i] = queryToRight(rightHullA, x, a[i], N)
			leftValB[i] = queryToRight(rightHullA, x, b[i], N)
		}
		prefB := make([]float64, leftCnt)
		prefB[0] = leftValB[0]
		for i := 1; i < leftCnt; i++ {
			prefB[i] = maxf(prefB[i-1], leftValB[i])
		}
		sufA := make([]float64, leftCnt+1)
		sufA[leftCnt] = negInf
		for i := leftCnt - 1; i >= 0; i-- {
			sufA[i] = maxf(leftValA[i], sufA[i+1])
		}
		for i := 0; i <= leftEnd; i++ {
			ans[i] = maxf(prefB[i], sufA[i+1])
		}

		leftHullB := buildHull(0, leftEnd, b)
		rightCnt := n - rightStart
		rightValA := make([]float64, rightCnt)
		rightValB := make([]float64, rightCnt)
		for idx, k := 0, rightStart; k < n; k, idx = k+1, idx+1 {
			x := int64(k)
			rightValA[idx] = queryToLeft(leftHullB, x, a[k], N)
			rightValB[idx] = queryToLeft(leftHullB, x, b[k], N)
		}
		prefB2 := make([]float64, rightCnt)
		prefB2[0] = rightValB[0]
		for i := 1; i < rightCnt; i++ {
			prefB2[i] = maxf(prefB2[i-1], rightValB[i])
		}
		sufA2 := make([]float64, rightCnt+1)
		sufA2[rightCnt] = negInf
		for i := rightCnt - 1; i >= 0; i-- {
			sufA2[i] = maxf(rightValA[i], sufA2[i+1])
		}
		for i := rightStart; i < n; i++ {
			idx := i - rightStart
			ans[i] = maxf(prefB2[idx], sufA2[idx+1])
		}
	} else {
		c := n / 2
		rightStart := c + 1

		rightHullA := buildHull(rightStart, n-1, a)
		leftValA := make([]float64, c)
		leftValB := make([]float64, c)
		for i := 0; i < c; i++ {
			x := int64(i)
			leftValA[i] = queryToRight(rightHullA, x, a[i], N)
			leftValB[i] = queryToRight(rightHullA, x, b[i], N)
		}
		prefB := make([]float64, c)
		prefB[0] = leftValB[0]
		for i := 1; i < c; i++ {
			prefB[i] = maxf(prefB[i-1], leftValB[i])
		}
		sufA := make([]float64, c+1)
		sufA[c] = negInf
		for i := c - 1; i >= 0; i-- {
			sufA[i] = maxf(leftValA[i], sufA[i+1])
		}
		centerA := 2.0 * float64(a[c])
		for i := 0; i < c; i++ {
			v := centerA
			v = maxf(v, prefB[i])
			v = maxf(v, sufA[i+1])
			ans[i] = v
		}

		centerB := 2.0 * float64(b[c])
		ans[c] = maxf(centerB, prefB[c-1])

		leftHullB := buildHull(0, c-1, b)
		rightCnt := n - rightStart
		rightValA := make([]float64, rightCnt)
		rightValB := make([]float64, rightCnt)
		for idx, k := 0, rightStart; k < n; k, idx = k+1, idx+1 {
			x := int64(k)
			rightValA[idx] = queryToLeft(leftHullB, x, a[k], N)
			rightValB[idx] = queryToLeft(leftHullB, x, b[k], N)
		}
		prefB2 := make([]float64, rightCnt)
		prefB2[0] = rightValB[0]
		for i := 1; i < rightCnt; i++ {
			prefB2[i] = maxf(prefB2[i-1], rightValB[i])
		}
		sufA2 := make([]float64, rightCnt+1)
		sufA2[rightCnt] = negInf
		for i := rightCnt - 1; i >= 0; i-- {
			sufA2[i] = maxf(rightValA[i], sufA2[i+1])
		}
		for i := rightStart; i < n; i++ {
			idx := i - rightStart
			v := centerB
			v = maxf(v, prefB2[idx])
			v = maxf(v, sufA2[idx+1])
			ans[i] = v
		}
	}

	var out bytes.Buffer
	for i := 0; i < n; i++ {
		if i > 0 {
			out.WriteByte(' ')
		}
		out.WriteString(strconv.FormatFloat(ans[i], 'f', 15, 64))
	}
	out.WriteByte('\n')
	os.Stdout.Write(out.Bytes())
}