← Home
For problem statement at 0-999/600-699/630-639/639/problemE.txt this is a correct solution, but verifier at 0-999/600-699/630-639/639/verifierE.go ends with case 1 failed: expected 0.793103448276 got 0.793103448
input:5
2 3 4 6 8
10 1 3 8 1
exit status 1 can you fix the verifier? package main

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

type Problem struct {
	P    int64
	t    int64
	MinX int64
	MaxX int64
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(reader, &n)

	probs := make([]*Problem, n)
	for i := 0; i < n; i++ {
		probs[i] = &Problem{}
		fmt.Fscan(reader, &probs[i].P)
	}

	var T int64
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &probs[i].t)
		T += probs[i].t
	}

	sort.Slice(probs, func(i, j int) bool {
		left := probs[i].P * probs[j].t
		right := probs[j].P * probs[i].t
		if left != right {
			return left > right
		}
		return probs[i].P < probs[j].P
	})

	var prefixT int64 = 0
	i := 0
	for i < n {
		j := i
		var groupT int64 = 0
		for j < n && probs[j].P*probs[i].t == probs[i].P*probs[j].t {
			groupT += probs[j].t
			j++
		}
		for k := i; k < j; k++ {
			probs[k].MinX = prefixT + probs[k].t
			probs[k].MaxX = prefixT + groupT
		}
		prefixT += groupT
		i = j
	}

	sort.Slice(probs, func(i, j int) bool {
		return probs[i].P < probs[j].P
	})

	vmin := make([]float64, n)
	vmax := make([]float64, n)
	sufMinVmax := make([]float64, n)

	check := func(c float64) bool {
		for k := 0; k < n; k++ {
			vmin[k] = float64(probs[k].P) * (1.0 - c*float64(probs[k].MinX)/float64(T))
			vmax[k] = float64(probs[k].P) * (1.0 - c*float64(probs[k].MaxX)/float64(T))
		}

		sufMinVmax[n-1] = vmax[n-1]
		for k := n - 2; k >= 0; k-- {
			if vmax[k] < sufMinVmax[k+1] {
				sufMinVmax[k] = vmax[k]
			} else {
				sufMinVmax[k] = sufMinVmax[k+1]
			}
		}

		maxVmin := vmin[0]
		for k := 0; k < n-1; k++ {
			if vmin[k] > maxVmin {
				maxVmin = vmin[k]
			}
			if probs[k].P < probs[k+1].P {
				if maxVmin > sufMinVmax[k+1] {
					return false
				}
			}
		}
		return true
	}

	low := 0.0
	high := 1.0
	for iter := 0; iter < 100; iter++ {
		mid := (low + high) / 2.0
		if check(mid) {
			low = mid
		} else {
			high = mid
		}
	}

	fmt.Printf("%.9f\n", low)
}