結果

問題 No.2094 Symmetry
ユーザー ID 21712
提出日時 2025-05-10 22:10:34
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 2,272 bytes
コンパイル時間 12,181 ms
コンパイル使用メモリ 244,852 KB
実行使用メモリ 10,280 KB
最終ジャッジ日時 2025-05-10 22:11:02
合計ジャッジ時間 27,085 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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])
		}
	}
	Println(solve(n,k,s,c))
}

func solve(n, k int, s [][]byte, c [][]int) int {
	ss := func(i int) byte { return s[i/n][i%n] }
	cc := func(i int) int { return c[i/n][i%n] }
	
	p := Perm(n*n)

	blacks := 0
	for i := range p {
		if ss(i) == '#' {
			blacks++
		}
	}
	
	// not care symmetry
	Slice(p, func(i, j int) bool {
		return cc(p[i]) > cc(p[j])
	})
	var ans int
	for _, pi := range p[:blacks] {
		ans += cc(pi)
	}

	if blacks%2 != 0 {
		println("cannot symmetry")
		return ans
	}
	
	if blacks == 0 {
		Println("not found blacks")
		return k
	}
	
	// care symmetry
	
	sym := func(i int) int { return i-i%n+(n-1-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
	tmp := k
	for _, pi := range p {
		if sym(pi) < pi {
			continue
		}
		tmp += cc(pi) + cc(sym(pi))
		cnt += 2
		if cnt >= blacks {
			break
		}
	}
	ans = max(ans, tmp)

	return ans
}

func init() {
	// check()
}

func check() {
	seed := Int63()
	println(Sprintf("seed = %d", seed))
	rng := New(NewSource(seed))
	n := rng.Intn(3) + 1
	k := rng.Intn(1e3)
	s := make([][]byte, 2*n)
	c := make([][]int, 2*n)
	blacks := 0
	for i := range s {
		s[i] = make([]byte, 2*n)
		for j := range s[i] {
			if rng.Intn(100) < 50 {
				s[i][j] = '#'
				blacks++
			} else {
				s[i][j] = '.'
			}
		}
	}
	for i := range c {
		c[i] = make([]int, 2*n)
		for j := range c[i] {
			c[i][j] = rng.Intn(1e2+1)-5e1
		}
	}
	println(Sprintf("%d %d", n, k))
	for _, line := range s {
		println(string(line))
	}
	for _, line := range c {
		for j, v := range line {
			if j > 0 {
				print(" ")
			}
			print(v)
		}
		println()
	}
	println(Sprintf("blacks=%d", blacks))
	println(Sprintf("can symmetry=%#v", blacks%2==0))
	println(solve(2*n,k,s,c))
}
0