小红的01子序列构造（hard）

package main

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

// 定义区间结构体
type Interval01 struct {
	l, r, x, y, k int
}

// 生成满足条件的字符串
func makeStr(x, k, l int) string {
	y := l - x
	if y == 0 {
		return strings.Repeat("0", l)
	}

	if k%y == 0 {
		return strings.Repeat("0", k/y) + strings.Repeat("1", y) + strings.Repeat("0", x-k/y)
	}

	return strings.Repeat("0", k/y) +
		strings.Repeat("1", y-k%y) +
		"0" +
		strings.Repeat("1", k%y) +
		strings.Repeat("0", x-k/y-1)
}

func main() {
	reader := bufio.NewReader(os.Stdin)

	// 读取输入
	line, _ := reader.ReadString('\n')
	parts := strings.Fields(line)
	length, _ := strconv.Atoi(parts[0])
	num, _ := strconv.Atoi(parts[1])

	// 读取限制条件
	limits := make([]Interval01, num)
	for i := 0; i < num; i++ {
		line, _ = reader.ReadString('\n')
		parts = strings.Fields(line)
		limits[i].l, _ = strconv.Atoi(parts[0])
		limits[i].r, _ = strconv.Atoi(parts[1])
		limits[i].x, _ = strconv.Atoi(parts[2])
		limits[i].y, _ = strconv.Atoi(parts[3])
		limits[i].k, _ = strconv.Atoi(parts[4])
	}

	// 按区间大小排序
	sort.Slice(limits, func(i, j int) bool {
		return (limits[i].r - limits[i].l) < (limits[j].r - limits[j].l)
	})

	// 处理第一个区间
	li, ri, xi, yi, ki := limits[0].l, limits[0].r, limits[0].x, limits[0].y, limits[0].k

	if ki > xi*yi {
		fmt.Println(-1)
		return
	}

	s := makeStr(xi, ki, ri-li+1)

	// 处理剩余区间
	for idx := 1; idx < num; idx++ {
		lj, rj, xj, yj, kj := limits[idx].l, limits[idx].r, limits[idx].x, limits[idx].y, limits[idx].k
		n, m := li-lj, rj-ri

		// 计算xa的范围
		L := getMax(0, xj-xi-m)
		R := getMin(n, xj-xi)
		if L > R {
			fmt.Println(-1)
			return
		}

		// 计算二次不等式系数
		A := xj + yi + n
		B := kj - ki - xj*(m+xi-xj)
		C := 2*xi + m + yi - xj
		D := kj - ki + xi*(xj-xi-m)

		// 检查判别式
		if A*A < 4*B || C*C < -4*D {
			fmt.Println(-1)
			return
		}

		// 解二次不等式
		left1 := (float64(A) - math.Sqrt(float64(A*A-4*B))) / 2
		right1 := (float64(A) + math.Sqrt(float64(A*A-4*B))) / 2
		left2 := (-math.Sqrt(float64(C*C+4*D)) - float64(C)) / 2
		right2 := (math.Sqrt(float64(C*C+4*D)) - float64(C)) / 2

		// 求交集
		left0 := int(math.Ceil(math.Max(left1, left2)))
		right0 := int(math.Floor(math.Min(right1, right2)))

		if left0 > right0 {
			fmt.Println(-1)
			return
		}

		// 求特解
		var xa int
		if left0 < L {
			if right0 >= L {
				xa = L
			} else {
				fmt.Println(-1)
				return
			}
		} else if left0 <= R {
			xa = left0
		} else {
			fmt.Println(-1)
			return
		}

		// 计算ka和kb
		ka := getMin(D-C*xa-xa*xa, xa*(n-xa))
		kb := getMax(0, D-C*xa-n*xa)
		xb := xj - xi - xa

		// 更新字符串
		s = makeStr(xa, ka, n) + s + makeStr(xb, kb, m)
		li, ri, xi, yi, ki = lj, rj, xj, yj, kj
	}

	// 补充前后缀
	if li > 1 {
		s = strings.Repeat("0", li-1) + s
	}
	if ri < length {
		s = s + strings.Repeat("0", length-ri)
	}

	fmt.Println(s)
}

// 辅助函数
func getMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func getMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}