#1051727 (Go) No.2596 Christmas Eve (Heuristic ver.)

• 問題: No.2596 Christmas Eve (Heuristic ver.)
• ユーザー: ID 21712
• 提出日時: 2025-03-11 13:04:26
• 言語: Go (1.23.4)
• 結果: AC
• 実行時間: 1,186 ms / 1,224 ms
• コード長: 7,253 bytes
• コンパイル時間: 12,924 ms
• コンパイル使用メモリ: 242,708 KB
• 実行使用メモリ: 20,096 KB
• スコア: 4,973,242
• 最終ジャッジ日時: 2025-03-11 13:07:21
• 合計ジャッジ時間: 173,531 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
other	AC * 125

ソースコード

package main

import (
	"cmp"
	. "fmt"
	"math/rand"
	"slices"
	"sort"
	"time"
	"bufio"
	"os"
)

type Unit struct {
	Id, Width, Height int
}

func solve(n, k int, a, b, c, d, e, f []int) (res [][]int) {
	ch := time.After(1180 * time.Millisecond)
	
	for i := range tops {
		tops[i] = &Unit{
			Id: i+1,
			Width: a[i],
			Height: b[i],
		}
	}

	for i := range leaves {
		leaves[i] = &Unit{
			Id: i+1,
			Width: c[i],
			Height: d[i],
		}
	}

	for i := range trunks {
		trunks[i] = &Unit{
			Id: i+1,
			Width: e[i],
			Height: f[i],
		}
	}
	slices.SortFunc(tops, func(a, b *Unit) int {
		return cmp.Compare(a.Width, b.Width)
	})
	slices.SortFunc(leaves, func(a, b *Unit) int {
		return cmp.Compare(a.Width, b.Width)
	})
	slices.SortFunc(trunks, func(a, b *Unit) int {
		return cmp.Compare(a.Width, b.Width)
	})

	for i, tru := range trunks {
		for j, tpu := range tops {
			if tru.Width < tpu.Width {
				trtps[i] = append(trtps[i], j)
				tptrs[j] = append(tptrs[j], i)
			}
		}
	}

	for i, tpu := range tops {
		for j, lvu := range leaves {
			if tpu.Width < lvu.Width {
				tplvs[i] = append(tplvs[i], j)
				lvtps[j] = append(lvtps[j], i)
			}
		}
	}
	connTrtps := make([]int, n)
	connTptrs := make([]int, n)
	connTplvs := make([][]int, n)
	connLvtps := make([]int, n*2)
	for i := range connTrtps {
		connTrtps[i] = -1
		connTptrs[i] = -1
		connTplvs[i] = []int{ -1, -1}
		connLvtps[i] = -1
		connLvtps[i+n] = -1
	}
	
outer1:
	for tri, tps := range trtps {
		if connTrtps[tri] >= 0 {
			continue
		}
		for _, tpi := range tps {
			if connTptrs[tpi] >= 0 {
				continue
			}
			for i, lv1i := range tplvs[tpi] {
				if connLvtps[lv1i] >= 0 {
					continue
				}
				for _, lv2i := range tplvs[tpi][i+1:] {
					if connLvtps[lv2i] >= 0 {
						continue
					}
					connTrtps[tri] = tpi
					connTptrs[tpi] = tri
					connTplvs[tpi][0] = lv1i
					connTplvs[tpi][1] = lv2i
					connLvtps[lv1i] = tpi
					connLvtps[lv2i] = tpi
					continue outer1
				}
			}
		}
	}
	
	height := func(tpi, lv1i, lv2i, tri int) int {
		return tops[tpi].Height+
			leaves[lv1i].Height+
			leaves[lv2i].Height+
			trunks[tri].Height
	}
	
	res = make([][]int, k)
	for i := range res {
		res[i] = make([]int, 4)
	}
	bestScore := int(1e9)
	
	makeResult := func() {
		i := 0
		for tpi, tri := range connTptrs {
			if tri < 0 {
				continue
			}
			lvs := connTplvs[tpi]
			tmp := res[i][:]
			tmp[0] = tops[tpi].Id
			tmp[1] = leaves[lvs[0]].Id
			tmp[2] = leaves[lvs[1]].Id
			tmp[3] = trunks[tri].Id
			i++
		}
	}
	
	combine := func(tpi, lv1i, lv2i, tri int) {
		// no validatation
		connTptrs[tpi] = tri
		connTplvs[tpi][0] = lv1i
		connTplvs[tpi][1] = lv2i
		connTrtps[tri] = tpi
		connLvtps[lv1i] = tpi
		connLvtps[lv2i] = tpi
	}
	
	destroy := func(tpi int) {
		tri := connTptrs[tpi]
		lvs := connTplvs[tpi]
		connTrtps[tri] = -1
		connLvtps[lvs[0]] = -1
		connLvtps[lvs[1]] = -1
		connTptrs[tpi] = -1
		lvs[0] = -1
		lvs[1] = -1
	}
	
	{
		founds := _founds[:0]
		for tpi, tri := range connTptrs {
			if tri < 0 {
				continue
			}
			founds = append(founds, tpi)
		}
		slices.SortFunc(founds, func(tpi1, tpi2 int) int {
			tri1 := connTptrs[tpi1]
			lvs1 := connTplvs[tpi1]
			h1 := height(tpi1, lvs1[0], lvs1[1], tri1)
			tri2 := connTptrs[tpi2]
			lvs2 := connTplvs[tpi2]
			h2 := height(tpi2, lvs2[0], lvs2[1], tri2)
			return cmp.Compare(h1, h2)
		})
		besti, bestd := -1, int(1e9)
		for i := 0; i+k <= len(founds); i++ {
			tpi1 := founds[i]
			tpi2 := founds[i+k-1]
			tri1 := connTptrs[tpi1]
			lvs1 := connTplvs[tpi1]
			h1 := height(tpi1, lvs1[0], lvs1[1], tri1)
			tri2 := connTptrs[tpi2]
			lvs2 := connTplvs[tpi2]
			h2 := height(tpi2, lvs2[0], lvs2[1], tri2)
			d := h2-h1
			if d < bestd {
				besti, bestd = i, d
			}
		}
		for i, tpi := range founds {
			if besti <= i && i < besti+k {
				continue
			}
			destroy(tpi)
		}
	}
	
	for tpi := range tphs {
		tri := connTptrs[tpi]
		if tri < 0 {
			continue
		}
		lvs := connTplvs[tpi]
		tphs[tpi] = height(tpi, lvs[0], lvs[1], tri)
	}

	trs := _trs[:]
	lvs := _lvs[:]
	for {
		select {
			case <-ch:
				return
			default:
		}
		mintpi, maxtpi := -1, -1
		minh, maxh := int(1e9), 0
		for tpi, tri := range connTptrs {
			if tri < 0 {
				continue
			}
			h := tphs[tpi]
			if h < minh {
				mintpi, minh = tpi, h
			}
			if h > maxh {
				maxtpi, maxh = tpi, h
			}
		}
		if maxh - minh < bestScore {
			bestScore = maxh - minh
			makeResult()
		}
		half := (maxh + minh) / 2
		if half - minh < maxh - half {
			destroy(maxtpi)
		} else {
			destroy(mintpi)
		}
		for {
			select {
				case <-ch:
					return
				default:
			}
			besttpi, besttri, bestlv1i, bestlv2i := -1,-1,-1,-1
			bestd, besth := int(1e9), 0
			for tpi, tri0 := range connTptrs {
				if tri0 >= 0 {
					continue
				}
				trs = trs[:0]
				for _, tri := range tptrs[tpi] {
					if connTrtps[tri] < 0 {
						trs = append(trs, tri)
					}
				}
				if len(trs) == 0 {
					continue
				}
				trc := min(len(trs), 4)
				trps := get(len(trs))[:trc]
				lvs := lvs[:0]
				for _, lvi := range tplvs[tpi] {
					if connLvtps[lvi] < 0 {
						lvs = append(lvs, lvi)
					}
				}
				if len(lvs) == 0 {
					continue
				}
				lvc := min(len(lvs), 4)
				lvps := get(len(lvs))[:lvc]
				for _, x := range trps {
					tri := trs[x]
					for i, y := range lvps {
						lv1i := lvs[y]
						for _, z := range lvps[i+1:] {
							lv2i := lvs[z]
							h := height(tpi, lv1i, lv2i, tri)
							if h <= minh || maxh <= h {
								continue
							}
							d := half - h
							if d < 0 {
								d = -d
							}
							if d < bestd {
								besttpi = tpi
								besttri = tri
								bestlv1i = lv1i
								bestlv2i = lv2i
								bestd = d
								besth = h
							}
						}
					}
				}
			}
			if besttpi >= 0 {
				combine(besttpi, bestlv1i, bestlv2i, besttri)
				tphs[besttpi] = besth
				break
			}
		}
	}

	return
}

func main() {
	rd := bufio.NewReader(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)
	defer wr.Flush()
	var n, k int
	Fscan(rd, &n, &k)
	a := make([]int, n)
	b := make([]int, n)
	c := make([]int, n*2)
	d := make([]int, n*2)
	e := make([]int, n)
	f := make([]int, n)
	for _, vs := range [][]int{a,b,c,d,e,f} {
		for i := range vs {
			Fscan(rd, &vs[i])
		}
	}
	ans := solve(n, k, a, b, c, d, e, f)
	for _, vs := range ans {
		Fprintln(wr, vs[0], vs[1], vs[2], vs[3])
	}
}

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

const N = 500

var (
	_tops [N]*Unit
	tops = _tops[:]
	_leaves [N*2]*Unit
	leaves = _leaves[:]
	_trunks [N]*Unit
	trunks = _trunks[:]
	_trtps [N][]int
	trtps = _trtps[:]
	_tptrs [N][]int
	tptrs = _tptrs[:]
	_tplvs [N][]int
	tplvs = _tplvs[:]
	_lvtps [N*2][]int
	lvtps = _lvtps[:]
	_connTptrs [N]int
	connTptrs = _connTptrs[:]
	_connTrtps [N]int
	connTrtps = _connTrtps[:]
	_connTplvs [N][]int
	connTplvs = _connTplvs[:]
	_connLvtps [N*2]int
	connLvtps = _connLvtps[:]
	_tphs [N]int
	tphs = _tphs[:]
	_founds [N]int
	_trs [N]int
	_lvs [N*2]int
)

var _perms [(N+2)*(N+1)/2]int
var perms [N+1][]int

func init() {
	tmp := _perms[:]
	for i := range perms[:] {
		p := tmp[:i]
		tmp = tmp[i+1:]
		for j := range p {
			p[j] = j
		}
		perms[i] = p
	}
}

func get(i int) []int {
	perm := perms[i]
	rand.Shuffle(i, func(i, j int) {
		sort.IntSlice(perm).Swap(i, j)
	})
	return perm
}