結果

問題 No.5004 Room Assignment
コンテスト
ユーザー ID 21712
提出日時 2025-03-06 23:20:13
言語 Go
(1.23.4)
結果
AC  
実行時間 336 ms / 5,000 ms
コード長 2,816 bytes
コンパイル時間 12,495 ms
コンパイル使用メモリ 238,188 KB
実行使用メモリ 26,228 KB
スコア 73,637,752
平均クエリ数 7334.89
最終ジャッジ日時 2025-03-06 23:21:03
合計ジャッジ時間 48,948 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

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

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

type Player struct {
	Id int
	Entered int
	Skill int
	*Room
}

type Room struct {
	Id int
	LastJoined int
	Endured int
	MinSkill, MaxSkill int
	Members []*Player
}

func (p *Player) MakeRoom(t int) *Room {
	return &Room {
		Id: p.Id,
		LastJoined: t,
		Endured: t - p.Entered,
		MinSkill: p.Skill,
		MaxSkill: p.Skill,
		Members: []*Player{p},
	}
}

func (r *Room) Count() int {
	return len(r.Members)
}

func (r *Room) Join(t int, p *Player) *Room {
	return &Room {
		Id: r.Id,
		LastJoined: t,
		Endured: r.Endured+(t-r.LastJoined)*r.Count()*(r.Count()+1)/2+(t-p.Entered)*r.Count(),
		MinSkill: min(r.MinSkill, p.Skill),
		MaxSkill: max(r.MaxSkill, p.Skill),
		Members: append([]*Player{p}, r.Members...),
	}
}

func (r *Room) Score() int {
	s := 200 - (r.MaxSkill-r.MinSkill)*(r.MaxSkill-r.MinSkill)
	switch r.Count() {
		default:
			return 0
		case 2:
			return s - r.Endured
		case 3:
			return 3 * s - r.Endured
		case 4:
			return 6 * s - r.Endured
	}
}

func main() {
	var t, r int
	Scan(&t, &r)
	rooms := []*Room{}
	ps := []*Player{}
	id := 0
	for ti := 0; ti < t; ti++ {
		{
			tmpRooms := []*Room{}
			for _, room := range rooms {
				if room.Count() < r {
					tmpRooms = append(tmpRooms, room)
				}
			}
			rooms = tmpRooms
		}
		{
			tmpPs := []*Player{}
			for _, p := range ps {
				if p.Room == nil && ti - p.Entered < 200  {
					tmpPs = append(tmpPs, p)
				}
			}
			ps = tmpPs
		}
		var n int
		Scan(&n)
		for i := 0; i < n; i++ {
			var s int
			Scan(&s)
			id++
			p := &Player{
				Id: id,
				Entered: ti,
				Skill: s,
				Room: nil,
			}
			ps = append(ps, p)
		}
		con := []int{}
		if len(ps) > 60 || ti+1 == t {
			for _, p := range ps {
				var best *Room
				var bestScore int
				for _, room := range rooms {
					tmpRoom := room.Join(ti, p)
					if sc := tmpRoom.Score(); sc > bestScore && sc > room.Score() {
						best = tmpRoom
						bestScore = sc
					}
				}
				for _, q := range ps {
					if q.Id == p.Id || q.Room != nil {
						continue
					}
					tmpRoom := q.MakeRoom(ti).Join(ti, p)
					if sc := tmpRoom.Score(); sc > bestScore {
						best = tmpRoom
						bestScore = sc
					}
				}
				if best != nil {
					found := false
					for i, room := range rooms {
						if room.Id == best.Id {
							rooms[i] = best
							found = true
							break
						}
					}
					if !found {
						rooms = append(rooms, best)
					}
					for _, p := range best.Members {
						if p.Room == nil && best.Id != p.Id {
							con = append(con, best.Id, p.Id)
						}
						p.Room = best
					}
				}
			}
		}
		Println(len(con)/2)
		for i := 0; i < len(con); i += 2 {
			Println(con[i], con[i+1])
		}
	}
}
0