結果

問題 No.5005 3-SAT
ユーザー ID 21712
提出日時 2025-02-11 13:41:13
言語 Go
(1.23.4)
結果
AC  
実行時間 1,838 ms / 2,000 ms
コード長 2,676 bytes
コンパイル時間 11,107 ms
コンパイル使用メモリ 234,952 KB
実行使用メモリ 6,820 KB
スコア 93,858
最終ジャッジ日時 2025-02-11 13:44:34
合計ジャッジ時間 200,047 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import "iter"
import "time"
import "math/rand"

const N = 2048
const M = 256

func main() {
	conds := make([]*Cond, 0, N)
	for i := 0; i < N; i++ {
		z := newCond(i)
		Scan(z)
		if z.IsNoEffect() {
			continue
		}
		conds = append(conds, z)
	}
	
	ch := time.After(time.Millisecond * 1800)
	
	search(ch, conds)
	
	realScore := 0
	for _, z := range conds {
		if z.IsOk(ans) {
			realScore = z.Id
		} else {
			break
		}
	}
	println(realScore)
	println(score)
	for _, v := range ans[:] {
		Print(v)
	}
	Println()
}

var ans = make([]int, M)
var score int

func calc(conds []*Cond, solution []int) (sc int) {
	for _, z := range conds {
		if z.IsOk(solution) {
			sc = z.Id
		} else {
			return
		}
	}
	return
}

func search(ch <-chan time.Time, conds []*Cond) {
	const B = 3
	tmp := make([]int, M)
	tmpScore := calc(conds, tmp)
	backup := make([]int, B)
	perm := rand.Perm(M)
	for {
		select {
			case <-ch:
				return
			default:
		}
		rand.Shuffle(len(perm), func(i, j int ) {
			perm[i],perm[j]=perm[j],perm[i]	
		})
		for i, p := range perm[:B] {
			backup[i] = tmp[p]
		}
		pics := rand.Intn(1<<B)
		for k := 0; k < B; k++ {
			tmp[perm[k]] = (pics >> k) & 1
		}
		sc := calc(conds, tmp)
		if sc < tmpScore {
			for i, p := range perm[:B] {
				tmp[p] = backup[i]
			}
			continue
		}
		tmpScore = sc
		if tmpScore > score {
			score = tmpScore
			ans = tmp
			tmp = make([]int, M)
			copy(tmp, ans)
		}
	}
}

type Cond struct {
	Id int
	factors [][]int
}

func newCond(id int) *Cond {
	return &Cond{id, make([][]int, 2)}
}

func (z *Cond) Ones() []int {
	return z.factors[1]
}

func (z *Cond) Zeros() []int {
	return z.factors[0]
}

func (z *Cond) Iter() iter.Seq2[int, int] {
	return func(yield func(k, v int) bool) {
		for p, fs := range z.factors {
			for _, a := range fs {
				if !yield(a, p) {
					return
				}
			}
		}
	}
}

func (z *Cond) IsNoEffect() bool {
	return len(z.Ones()) == 0 && len(z.Zeros()) == 0
}

func (z *Cond) IsOk(solution []int) bool {
	for i, fs := range z.factors {
		for _, a := range fs {
			if solution[a] == i {
				return true
			}
		}
	}
	return false
}

func (z *Cond) add(a, p int) {
	z.factors[p] = append(z.factors[p], a)
}

func (z *Cond) Scan(s ScanState, v rune) error {
	var a,b,c,p,q,r int
	Fscan(s,&a,&b,&c,&p,&q,&r)
	a,b,c = M-1-a,M-1-b,M-1-c
	switch {
		case a == b && b == c:
			if p == q && q == r {
				z.add(a, p)
			}
		case a == b:
			if p == q {
				z.add(a, p)
				z.add(c, r)
			}
		case a == c:
			if p == r {
				z.add(a, p)
				z.add(b, q)
			}
		case b == c:
			if q == r {
				z.add(a, p)
				z.add(b, q)
			}
		default:
			z.add(a, p)
			z.add(b, q)
			z.add(c, r)
	}
	return nil
}
0