結果

問題 No.5005 3-SAT
ユーザー ID 21712
提出日時 2025-02-13 02:58:49
言語 Go
(1.23.4)
結果
AC  
実行時間 1,841 ms / 2,000 ms
コード長 2,468 bytes
コンパイル時間 10,982 ms
コンパイル使用メモリ 236,096 KB
実行使用メモリ 6,824 KB
スコア 97,180
最終ジャッジ日時 2025-02-13 03:02:11
合計ジャッジ時間 200,328 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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) {
	tmp := make([]int, M)
	for i := range tmp {
		tmp[i] = rand.Intn(2)
	}
	tmpScore := calc(conds, tmp)
	for {
		select {
			case <-ch:
				return
			default:
		}
		i := rand.Intn(M)
		j := rand.Intn(M)
		if i == j {
			j = (i+1)%M
		}
		tmp[i] ^= 1
		tmp[j] ^= 1
		sc := calc(conds, tmp)
		if sc < tmpScore {
			tmp[i] ^= 1
			tmp[j] ^= 1
		} else {
			tmpScore = sc
			if tmpScore > score {
				score = tmpScore
				copy(ans, tmp)
			}
		}
	}
}

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