結果

問題 No.5005 3-SAT
ユーザー ID 21712
提出日時 2025-02-11 00:36:36
言語 Go
(1.23.4)
結果
AC  
実行時間 1,856 ms / 2,000 ms
コード長 2,913 bytes
コンパイル時間 16,490 ms
コンパイル使用メモリ 237,172 KB
実行使用メモリ 6,820 KB
スコア 78,181
最終ジャッジ日時 2025-02-11 00:40:04
合計ジャッジ時間 203,970 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import "iter"
import "time"
import "context"

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)
	}
	
	ctx, cancel := context.WithTimeout(context.Background(), time.Millisecond * 1800)
	defer cancel()
	
	search(ctx, conds)
	
	realScore := 0
	for i, z := range conds {
		if z.IsOk(ans) {
			realScore = i
		} else {
			break
		}
	}
	println(realScore)
	println(score)
	for _, v := range ans[:] {
		Print(v)
	}
	Println()
}

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

func search(ctx context.Context, conds []*Cond) {
	edges := make([][][]int, M)
	for i := range edges {
		edges[i] = make([][]int, 2)
	}
	for i, z := range conds {
		for a, p := range z.Iter() {
			edges[a][p] = append(edges[a][p], i)
		}
	}
	count := 0
	changed := make([]int, M)
	tmp := make([]int, M)
	pos := 0
	for pos < len(conds) {
		select {
			case <-ctx.Done():
				return
			default:
		}
		z := conds[pos]
		ok := false
		min, mina, minp := count+1, 0, 0
		for a, p := range z.Iter() {
			if tmp[a] == p {
				ok = true
				break
			}
			if changed[a] < min {
				min, mina, minp = changed[a], a, p
			}
		}
		if ok {
			if pos > score {
				score = pos
				ans = tmp
				tmp = make([]int, M)
				copy(tmp, ans)
			}
			pos++
			continue
		}
		pos++
		count++
		changed[mina] = count
		tmp[mina] = minp
		for _, i := range edges[mina][1-minp] {
			if i > pos {
				break
			}
			if !conds[i].IsOk(tmp) {
				pos = i
				break
			}
		}
		if pos > score {
			score = pos
			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