← Home
For problem statement at 0-999/300-399/300-309/303/problemE.txt this is a correct solution, but verifier at 0-999/300-399/300-309/303/verifierE.go ends with test 1 failed
expected: 1.0000000000
 got: 1.000000000
exit status 1 can you fix the verifier? package main

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

type State struct {
	dp [81][81]float64
}

func add(src, dst *State, p_lt, p_eq, p_gt float64, count int) {
	for j := 0; j <= count+1; j++ {
		for k := 0; k <= count+1-j; k++ {
			dst.dp[j][k] = 0
		}
	}
	for j := 0; j <= count; j++ {
		for k := 0; k <= count-j; k++ {
			val := src.dp[j][k]
			if val == 0 {
				continue
			}
			if p_gt > 0 {
				dst.dp[j][k] += val * p_gt
			}
			if p_lt > 0 {
				dst.dp[j+1][k] += val * p_lt
			}
			if p_eq > 0 {
				dst.dp[j][k+1] += val * p_eq
			}
		}
	}
}

func solve(L, R int, current_dp *State, current_count int, U []int, ans [][]float64, B int, delta float64, L_arr, R_arr []float64, x_k, x_k1 float64) {
	if L == R {
		u := U[L]
		p_in := delta / (R_arr[u] - L_arr[u])
		for j := 0; j <= current_count; j++ {
			for k := 0; k <= current_count-j; k++ {
				val := current_dp.dp[j][k]
				if val == 0 {
					continue
				}
				prob := val * p_in / float64(k+1)
				for r := 0; r <= k; r++ {
					ans[u][j+B+r] += prob
				}
			}
		}
		return
	}

	mid := (L + R) / 2

	var left_dp State
	for j := 0; j <= current_count; j++ {
		for k := 0; k <= current_count-j; k++ {
			left_dp.dp[j][k] = current_dp.dp[j][k]
		}
	}

	dp_ptr := &left_dp
	var next_left_dp State
	next_ptr := &next_left_dp
	cnt := current_count
	for i := mid + 1; i <= R; i++ {
		u := U[i]
		p_lt := (x_k - L_arr[u]) / (R_arr[u] - L_arr[u])
		if p_lt < 0 {
			p_lt = 0
		}
		p_eq := delta / (R_arr[u] - L_arr[u])
		p_gt := (R_arr[u] - x_k1) / (R_arr[u] - L_arr[u])
		if p_gt < 0 {
			p_gt = 0
		}

		add(dp_ptr, next_ptr, p_lt, p_eq, p_gt, cnt)
		dp_ptr, next_ptr = next_ptr, dp_ptr
		cnt++
	}
	solve(L, mid, dp_ptr, cnt, U, ans, B, delta, L_arr, R_arr, x_k, x_k1)

	var right_dp State
	for j := 0; j <= current_count; j++ {
		for k := 0; k <= current_count-j; k++ {
			right_dp.dp[j][k] = current_dp.dp[j][k]
		}
	}

	dp_ptr2 := &right_dp
	var next_right_dp State
	next_ptr2 := &next_right_dp
	cnt = current_count
	for i := L; i <= mid; i++ {
		u := U[i]
		p_lt := (x_k - L_arr[u]) / (R_arr[u] - L_arr[u])
		if p_lt < 0 {
			p_lt = 0
		}
		p_eq := delta / (R_arr[u] - L_arr[u])
		p_gt := (R_arr[u] - x_k1) / (R_arr[u] - L_arr[u])
		if p_gt < 0 {
			p_gt = 0
		}

		add(dp_ptr2, next_ptr2, p_lt, p_eq, p_gt, cnt)
		dp_ptr2, next_ptr2 = next_ptr2, dp_ptr2
		cnt++
	}
	solve(mid+1, R, dp_ptr2, cnt, U, ans, B, delta, L_arr, R_arr, x_k, x_k1)
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1024*1024), 1024*1024)

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())
	if n == 0 {
		return
	}

	L_arr := make([]float64, n)
	R_arr := make([]float64, n)
	endpoints := make([]float64, 0, 2*n)

	for i := 0; i < n; i++ {
		scanner.Scan()
		L_arr[i], _ = strconv.ParseFloat(scanner.Text(), 64)
		scanner.Scan()
		R_arr[i], _ = strconv.ParseFloat(scanner.Text(), 64)
		endpoints = append(endpoints, L_arr[i], R_arr[i])
	}

	sort.Float64s(endpoints)
	uniqueEndpoints := make([]float64, 0, len(endpoints))
	for i, v := range endpoints {
		if i == 0 || v != endpoints[i-1] {
			uniqueEndpoints = append(uniqueEndpoints, v)
		}
	}

	ans := make([][]float64, n)
	for i := 0; i < n; i++ {
		ans[i] = make([]float64, n)
	}

	for i := 0; i < len(uniqueEndpoints)-1; i++ {
		x_k := uniqueEndpoints[i]
		x_k1 := uniqueEndpoints[i+1]
		delta := x_k1 - x_k
		if delta == 0 {
			continue
		}

		U := make([]int, 0, n)
		B := 0
		for u := 0; u < n; u++ {
			if L_arr[u] <= x_k && x_k1 <= R_arr[u] {
				U = append(U, u)
			} else if R_arr[u] <= x_k {
				B++
			}
		}

		if len(U) > 0 {
			var start_dp State
			start_dp.dp[0][0] = 1.0
			solve(0, len(U)-1, &start_dp, 0, U, ans, B, delta, L_arr, R_arr, x_k, x_k1)
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if j > 0 {
				fmt.Printf(" ")
			}
			fmt.Printf("%.9f", ans[i][j])
		}
		fmt.Println()
	}
}