結果

問題 No.2094 Symmetry
ユーザー ID 21712
提出日時 2025-05-10 20:11:10
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 2,010 bytes
コンパイル時間 11,630 ms
コンパイル使用メモリ 237,948 KB
実行使用メモリ 16,200 KB
最終ジャッジ日時 2025-05-10 20:11:26
合計ジャッジ時間 15,848 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 1 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "sort"
import . "math/rand"

func main() {
	var n, k int
	Scan(&n, &k)
	n *= 2
	s := make([][]byte, n)
	for i := range s {
		var str string
		Scan(&str)
		s[i] = []byte(str)
	}
	c := make([][]int, n)
	for i := range c {
		c[i] = make([]int, n)
		for j := range c[i] {
			Scan(&c[i][j])
		}
	}
	ss := func(i int) byte { return s[i/n][i%n] }
	cc := func(i int) int { return c[i/n][i%n] }
	
	// not care symmetry
	p := Perm(n*n)
	Slice(p, func(i, j int) bool {
		return cc(p[i]) < cc(p[j])
	})
	var ans int
	for i,j := 0, len(p)-1; i <= j; {
		pi, pj := p[i], p[j]
		if i < j {
			switch {
				case ss(pi) == '.':
					i++
				case ss(pj) == '#':
					ans += cc(pj)
					j--
				default:
					ans += cc(pj)
					i++
					j--
			}
		} else {
			if ss(i) == '#' {
				ans += cc(i)
			}
			break
		}
	}
	
	// care symmetry
	
	sym := func(i int) int { return i-i%n+(n-1-i%n) }
	swap := func(i int) { s[i/n][i%n] = '#'+'.' - s[i/n][i%n] }
	
	Slice(p, func(i, j int) bool {
		return cc(p[i])+cc(sym(p[i])) < cc(p[j])+cc(sym(p[j]))
	})
	
	for i, j := 0, len(p)-1; i < j; {
		pi, pj := p[i], p[j]
		switch {
			case sym(pi) < pi:
				i++
			case sym(pj) < pj:
				j--
			case pi == sym(pj) || pj == sym(pi):
				panic("bug")
			case ss(pi) == '.' && ss(sym(pi)) == '.':
				i++
			case ss(pj) == '#' && ss(sym(pj)) == '#':
				j--
			default:
				if ss(pi) == '#' {
					if ss(pj) == '.' {
						swap(pi)
						swap(pj)
					} else if ss(sym(pj)) == '.' {
						swap(pi)
						swap(sym(pj))
					} else {
						panic("bug")
					}
				} else if ss(sym(pi)) == '#' {
					if ss(pj) == '.' {
						swap(sym(pi))
						swap(pj)
					} else if ss(sym(pj)) == '.' {
						swap(sym(pi))
						swap(sym(pj))
					} else {
						panic("bug")
					}
				} else {
					panic("bug")
				}
		}
	}
	tmp := k
	issym := true
	for i := range p {
		if ss(i) != ss(sym(i)) {
			issym = false
			break
		}
		if ss(i) == '#' {
			tmp += cc(i)
		}
	}
	if issym {
		ans = max(ans, tmp)
	}

	Println(ans)
}
0