結果

問題 No.5005 3-SAT
ユーザー ID 21712
提出日時 2025-02-04 03:48:05
言語 Go
(1.23.4)
結果
AC  
実行時間 1,022 ms / 2,000 ms
コード長 1,447 bytes
コンパイル時間 18,583 ms
コンパイル使用メモリ 234,700 KB
実行使用メモリ 6,996 KB
スコア 45,374
最終ジャッジ日時 2025-02-04 03:50:01
合計ジャッジ時間 115,553 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import "math/rand"

const (
	N = 2048
	M = 256
)

type Cond struct {
	a,b,c,p,q,r int
}

func (c *Cond)Scan(s ScanState, v rune) error {
	Fscan(s, &c.a, &c.b, &c.c, &c.p, &c.q, &c.r)
	c.a,c.b,c.c = M-1-c.a,M-1-c.b,M-1-c.c
	return nil
}

func main() {
	conds := make([]*Cond, N)
	for i := range conds {
		conds[i] = new(Cond)
		Scan(conds[i])
	}
	
	ans := make([]int, M)
	best := 0
	
	for i := 0; i < 40000; i++ {
		tmp, score := fill(conds)
		if score > best {
			ans,best = tmp,score
		}
	}

	for _, x := range ans {
		Print(x)
	}
	Println()
}

func fill(conds []*Cond) (ans []int, score int) {
	ans = make([]int, M)
	filled := make([]bool, M)
	score = N
	block1:
	for i, c := range conds {
		if filled[c.a] && ans[c.a] == c.p {
			continue
		}
		if filled[c.b] && ans[c.b] == c.q {
			continue
		}
		if filled[c.c] && ans[c.c] == c.r {
			continue
		}
		if c.a == c.b && c.p != c.q {
			continue
		}
		if c.a == c.c && c.p != c.r {
			continue
		}
		if c.b == c.c && c.q != c.r {
			continue
		}
		for _, x := range rand.Perm(3) {
			switch x {
				case 0:
					if !filled[c.a] {
						ans[c.a] = c.p
						filled[c.a] = true
						continue block1
					}
				case 1:
					if !filled[c.b] {
						ans[c.b] = c.q
						filled[c.b] = true
						continue block1
					}
				case 2:
					if !filled[c.c] {
						ans[c.c] = c.r
						filled[c.c] = true
						continue block1
					}
			}
		}
		score = i
		break
	}
	return
}
0