結果

問題 No.5004 Room Assignment
ユーザー ID 21712
提出日時 2025-03-06 22:21:52
言語 Go
(1.23.4)
結果
AC  
実行時間 294 ms / 5,000 ms
コード長 3,667 bytes
コンパイル時間 11,688 ms
コンパイル使用メモリ 238,288 KB
実行使用メモリ 26,356 KB
スコア 76,747,628
平均クエリ数 7078.61
最終ジャッジ日時 2025-03-06 22:22:38
合計ジャッジ時間 44,688 ms
ジャッジサーバーID
（参考情報） 		judge3 / 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 < 20  {
					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{}
		for _, p := range ps {
			var best *Room
			var bestScore int = 180
			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
				}
			}
		}
		for _, p := range ps {
			var best *Room
			var bestScore int
			if ti - p.Entered < 15 {
				continue
			}
			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 || ti - q.Entered < 15 {
					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