結果

問題 No.5005 3-SAT
ユーザー ID 21712
提出日時 2025-02-11 12:48:09
言語 Go
(1.23.4)
結果
AC  
実行時間 1,841 ms / 2,000 ms
コード長 3,697 bytes
コンパイル時間 11,688 ms
コンパイル使用メモリ 238,204 KB
実行使用メモリ 6,824 KB
スコア 75,700
最終ジャッジ日時 2025-02-11 12:51:31
合計ジャッジ時間 200,378 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

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 search(ch <-chan time.Time, 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 := M
	changed := rand.Perm(M)
	tmp := make([]int, M)
	for i := range conds {
		for a, p := range conds[len(conds)-1-i].Iter() {
			tmp[a] = p
			if rand.Intn(100) < 40 {
				break
			}
		}
	}
	max := len(conds)/2
	pos1, pos2 := 0, max
	phase := false
	for pos1 < len(conds) || pos2 >= 0 {
		if pos2 < pos1 {
			pos1 = max+1
			pos2 = max+1
		}
		pos := pos1
		phase = max-pos2 > pos1
		if phase {
			if pos2 >= 0 {
				pos = pos2
			} else {
				phase = !phase
			}
		}
		select {
			case <-ch:
				println(Sprintf("%d %d", pos1, pos2))
				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 || (changed[a] < count && rand.Intn(100) < 50) {
				min, mina, minp = changed[a], a, p
			}
		}
		if ok {
			if pos1 > score {
				score = pos1
				ans = tmp
				tmp = make([]int, M)
				copy(tmp, ans)
				if pos1 >= max {
					max = pos1
				}
			}
			if phase {
				pos2--
			} else {
				pos1++
			}
			continue
		}
		if phase {
			pos2--
		} else {
			pos1++
		}
		count++
		changed[mina] = count
		tmp[mina] = minp
		for _, i := range edges[mina][1-minp] {
			if i > pos1 {
				break
			}
			if !conds[i].IsOk(tmp) {
				pos1 = i
				break
			}
		}
		for _, i := range slices.Backward(edges[mina][1-minp]) {
			if i > max {
				continue
			}
			if i < pos2 {
				break
			}
			if !conds[i].IsOk(tmp) {
				pos2 = i
				break
			}
		}
		if pos1 > score {
			score = pos1
			ans = tmp
			tmp = make([]int, M)
			copy(tmp, ans)
			if pos1 >= max {
				max = pos1
			}
		}
	}
}

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