結果

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

ソースコード

diff # 

package main

import . "fmt"
import . "sort"
import . "math/rand"
import . "os"
import bf "bufio"

func assert(test bool, msg ...any) {
	if !test {
		if len(msg) > 0 {
			println(Sprint(msg...))
		}
		panic("assert")
	}
}

func main() {
	rd := bf.NewReader(Stdin)
	var n, k int
	Fscan(rd,&n, &k)
	n *= 2
	s := make([][]byte, n)
	for i := range s {
		var str string
		Fscan(rd,&str)
		s[i] = []byte(str)
	}
	c := make([][]int, n)
	for i := range c {
		c[i] = make([]int, n)
		for j := range c[i] {
			Fscan(rd,&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])
	})
	cnt := 0
	var ans int
	for i,j := 0, len(p)-1; i <= j; {
		pi, pj := p[i], p[j]
		cnt++
		assert(cnt <= 2*len(p))
		if i < j {
			switch {
				case ss(pi) == '.':
					i++
				case ss(pj) == '#':
					ans += cc(pj)
					j--
				default:
					// {pi,pj} = {'#','.'}
					assert(ss(pi) == '#')
					assert(ss(pj) == '.')
					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]))
	})
	
	cnt = 0
	for i, j := 0, len(p)-1; i < j; {
		pi, pj := p[i], p[j]
		cnt++
		assert(cnt <= 4*len(p))
		switch {
			case sym(pi) < pi:
				i++
			case sym(pj) < pj:
				j--
			case ss(pi) == '.' && ss(sym(pi)) == '.':
				i++
			case ss(pj) == '#' && ss(sym(pj)) == '#':
				j--
			default:
				assert(pi != pj)
				assert(pi != sym(pi))
				assert(pj != sym(pj))
				assert(pi != sym(pj))
				assert(pj != sym(pi))
				assert(sym(pi) != sym(pj))
				// {pi,sym(pi)} = {'.','#'},{'#','.'},{'#','#'}
				// {pj,sym(pj)} = {'.','#'},{'#','.'},{'.','.'}
				assert(ss(pi)=='#'||ss(sym(pi))=='#')
				assert(ss(pj)=='.'||ss(sym(pj))=='.')
				if ss(pi) == '#' {
					if ss(pj) == '.' {
						swap(pi)
						swap(pj)
						assert(ss(pi) == '.')
						assert(ss(pj) == '#')
					} else if ss(sym(pj)) == '.' {
						swap(pi)
						swap(sym(pj))
						assert(ss(pi) == '.')
						assert(ss(sym(pj)) == '#')
					} else {
						panic("bug")
					}
				} else if ss(sym(pi)) == '#' {
					if ss(pj) == '.' {
						swap(sym(pi))
						swap(pj)
						assert(ss(sym(pi)) == '.')
						assert(ss(pj) == '#')
					} else if ss(sym(pj)) == '.' {
						swap(sym(pi))
						swap(sym(pj))
						assert(ss(sym(pi)) == '.')
						assert(ss(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