結果

問題 No.2596 Christmas Eve (Heuristic ver.)
ユーザー ID 21712
提出日時 2025-03-07 00:41:21
言語 Go
(1.23.4)
結果
AC  
実行時間 192 ms / 1,224 ms
コード長 4,787 bytes
コンパイル時間 12,674 ms
コンパイル使用メモリ 234,648 KB
実行使用メモリ 8,608 KB
スコア 4,270,681
最終ジャッジ日時 2025-03-07 00:42:04
合計ジャッジ時間 43,044 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 125
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import "sort"

type Unit struct {
	Id, Width, Height, Order int
	Used bool
	SetId int
}

func main() {
	var n, k int
	Scan(&n, &k)
	tops := make([]*Unit, n)
	bodies := make([]*Unit, n*2)
	bottoms := make([]*Unit, n)
	for i := range tops {
		u := new(Unit)
		u.Id = i+1
		Scan(&u.Width)
		tops[i] = u
	}
	for _, u := range tops {
		Scan(&u.Height)
	}
	for i := range bodies {
		u := new(Unit)
		u.Id = i+1
		Scan(&u.Width)
		bodies[i] = u
	}
	for _, u := range bodies {
		Scan(&u.Height)
	}
	for i := range bottoms {
		u := new(Unit)
		u.Id = i+1
		Scan(&u.Width)
		bottoms[i] = u
	}
	for _, u := range bottoms {
		Scan(&u.Height)
	}
	sort.Slice(tops, func(i, j int) bool {
		return tops[i].Width < tops[j].Width
	})
	sort.Slice(bodies, func(i, j int) bool {
		return bodies[i].Width < bodies[j].Width
	})
	sort.Slice(bottoms, func(i, j int) bool {
		return bottoms[i].Width < bottoms[j].Width
	})
	for i, u := range tops {
		u.Order = i
	}
	for i, u := range bodies {
		u.Order = i
	}
	for i, u := range bottoms {
		u.Order = i
	}
	sets := make([][]*Unit, 0, k)
	for _, btm := range bottoms[:k] {
		var top *Unit
		for len(tops) > 0 && top == nil {
			if tops[0].Width > btm.Width {
				top = tops[0]
			}
			tops = tops[1:]
		}
		body := make([]*Unit, 0, 2)
		for len(bodies) > 0 && len(body) < 2 {
			tmp := bodies[0]
			if top.Width < tmp.Width {
				body = append(body, tmp)
			}
			bodies = bodies[1:]
		}
		sets = append(sets, []*Unit{top, body[0], body[1], btm})
	}
	for i, us := range sets {
		for _, u := range us {
			u.Used = true
			u.SetId = i
		}
	}
outer:
	for q := 0; q < 20000; q++ {
		hmax, hmin := 0, int(1e9)
		maxi, mini := 0, 0
		for i, s := range sets {
			h := sum(s)
			if h > hmax {
				maxi = i
				hmax = h
			}
			if h < hmin {
				mini = i
				hmin = h
			}
		}
		for _, u := range bodies {
			if !u.Used {
				{
					h0 := sum(sets[mini])
					bk := sets[mini][1]
					sets[mini][1] = u
					if !valid(sets[mini]) {
						sets[mini][1] = bk
						continue
					}
					h1 := sum(sets[mini])
					if h1 > h0 && h1 < hmax {
						bk.Used = false
						u.Used = true
						u.SetId = mini
						continue outer
					} else {
						sets[mini][1] = bk
					}
				}
				{
					h0 := sum(sets[mini])
					bk := sets[mini][2]
					sets[mini][2] = u
					if !valid(sets[mini]) {
						sets[mini][2] = bk
						continue
					}
					h1 := sum(sets[mini])
					if h1 > h0 && h1 < hmax {
						bk.Used = false
						u.Used = true
						u.SetId = mini
						continue outer
					} else {
						sets[mini][2] = bk
					}
				}
			} else {
				for x:=1;x<=2;x++{
				for y:=1;y<=2;y++{
					si := u.SetId
					sets[mini][x],sets[si][y]=sets[si][y],sets[mini][x]
					if !valid(sets[mini])||!valid(sets[si]) {
						sets[mini][x],sets[si][y]=sets[si][y],sets[mini][x]
						continue
					}
					h0 := sum(sets[mini])
					h1 := sum(sets[si])
					if hmin < h0 && h0 < hmax && hmin < h1 && h1 < hmax {
						sets[mini][x].SetId = mini
						sets[si][y].SetId = si
						continue outer
					} else {
						sets[mini][x],sets[si][y]=sets[si][y],sets[mini][x]
					}
				}}
			}
		}
		for _, u := range bodies {
			if !u.Used {
				{
					h0 := sum(sets[maxi])
					bk := sets[maxi][1]
					sets[maxi][1] = u
					if !valid(sets[maxi]) {
						sets[maxi][1] = bk
						continue
					}
					h1 := sum(sets[maxi])
					if h1 < h0 && h1 > hmin {
						bk.Used = false
						u.Used = true
						u.SetId = maxi
						continue outer
					} else {
						sets[maxi][1] = bk
					}
				}
				{
					h0 := sum(sets[maxi])
					bk := sets[maxi][2]
					sets[maxi][2] = u
					if !valid(sets[maxi]) {
						sets[maxi][2] = bk
						continue
					}
					h1 := sum(sets[maxi])
					if h1 < h0 && h1 > hmin {
						bk.Used = false
						u.Used = true
						u.SetId = maxi
						continue outer
					} else {
						sets[maxi][2] = bk
					}
				}
			} else {
				for x:=1;x<=2;x++{
				for y:=1;y<=2;y++{
					si := u.SetId
					sets[maxi][x],sets[si][y]=sets[si][y],sets[maxi][x]
					if !valid(sets[maxi])||!valid(sets[si]) {
						sets[maxi][x],sets[si][y]=sets[si][y],sets[maxi][x]
						continue
					}
					h0 := sum(sets[maxi])
					h1 := sum(sets[si])
					if hmin < h0 && h0 < hmax && hmin < h1 && h1 < hmax {
						sets[maxi][x].SetId = maxi
						sets[si][y].SetId = si
						continue outer
					} else {
						sets[maxi][x],sets[si][y]=sets[si][y],sets[maxi][x]
					}
				}}
			}
		}
	}
	for _, s := range sets {
		Println([]any{s[0].Id, s[1].Id, s[2].Id, s[3].Id}...)
	}
}

func abs(a int) int {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

func valid(us []*Unit) bool {
	return us[0].Width > us[3].Width && us[1].Width > us[0].Width && us[2].Width > us[0].Width
}

func sum(us []*Unit) (h int) {
	for _, u := range us {
		h += u.Height
	}
	return
}
0