#1021384 (Go) No.1743 Permutation Code

• 問題: No.1743 Permutation Code
• ユーザー: ID 21712
• 提出日時: 2024-10-20 15:04:23
• 言語: Go (1.22.1)
• 結果: WA
• 実行時間: -
• コード長: 14,090 bytes
• コンパイル時間: 12,395 ms
• コンパイル使用メモリ: 225,200 KB
• 実行使用メモリ: 291,120 KB
• 最終ジャッジ日時: 2024-10-20 15:07:04
• 合計ジャッジ時間: 159,216 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,820 KB
testcase_03	AC	5 ms; 6,824 KB
testcase_04	AC	5 ms; 6,820 KB
testcase_05	AC	2 ms; 6,820 KB
testcase_06	AC	26 ms; 8,388 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	--	-

ソースコード

package main

import (
	"container/heap"
	. "fmt"
	"math/bits"
	"math/rand"
	"sort"
	"time"
)

// type any = interface{} // for old go version

func main() {
	var input string
	Scan(&input)
	if input == "LOCAL" {
		runLocal()
		return
	}
	s := NewSolver(input)
	s.Solve()
	ans := s.Answer()
	for i, v := range ans {
		if i > 0 {
			Print(" ")
		}
		Print(v)
	}
	Println()
}

func runLocal() {
	var n int
	Scan(&n)
	src := generate(n)
	code := encrypto(src)
	Println("N = ", n, ", |S| =", len(code), ", B = ", len(Sprintf("%b", n)))
	t := time.Now()
	s := NewSolver(code)
	s.Solve()
	ans := s.Answer()
	Println(time.Since(t))
	m := map[int]bool{}
	for _, v := range ans {
		m[v] = true
	}
	ok := len(ans) == len(src)
	for i := range ans {
		ok = ok && m[i+1]
	}
	result := encrypto(ans)
	if ok && code == result {
		Println("AC")
	} else {
		Println("WA")
	}
	if n < 100 {
		Println(src)
		if len(code) < 200 {
			Println(code)
		}
	}
	if n < 100 {
		Println(ans)
		if len(code) < 200 {
			Println(result)
		}
	}
}

func perm0(n int) []int {
	a := make([]int, n, n)
	for i := range a {
		a[i] = i
	}
	return a
}

func encrypto(src []int) string {
	s := ""
	for _, v := range src {
		s = Sprintf("%s%b", s, v)
	}
	return s
}

func generate(n int) []int {
	src := perm0(n + 1)[1:]
	rand.Shuffle(len(src), func(i, j int) {
		src[i], src[j] = src[j], src[i]
	})
	return src
}

func guessN(code string) (n int, bit uint) {
	totalbits := 0
	for ; ; bit++ {
		ibitsum := int(bit+1) * (1 << bit)
		if totalbits+ibitsum > len(code) {
			rem := (len(code) - totalbits) / int(bit+1)
			if rem > 0 {
				n += rem
				bit++
			}
			return
		}
		totalbits += ibitsum
		n += 1 << bit
	}
}

type Solver struct {
	code  string
	n     int
	bit   uint
	found []bool
	line  []int
	used  []int
}

func NewSolver(code string) *Solver {
	n, bit := guessN(code)
	found := make([]bool, n+1, n+1)
	line := make([]int, len(code), len(code))
	used := make([]int, len(code), len(code))
	return &Solver{code, n, bit, found, line, used}
}

func (s *Solver) Clone() *Solver {
	code, n, bit := s.code, s.n, s.bit
	found := make([]bool, n+1, n+1)
	copy(found, s.found)
	line := make([]int, len(code), len(code))
	copy(line, s.line)
	used := make([]int, len(code), len(code))
	copy(used, s.used)
	return &Solver{code, n, bit, found, line, used}
}

func (s *Solver) Answer() []int {
	ans := make([]int, 0, s.n)
	for _, v := range s.line {
		if v > 0 {
			ans = append(ans, v)
		}
	}
	return ans
}

func (s *Solver) Solve() {
	// s.analyze()
	s.fillfill()
	ch := make(chan *Solver)
	go s.doRandomFill(ch)
	result := <-ch
	if result != nil {
		copy(s.line, result.line)
	}
}

func (s *Solver) solveOld() {
	for n, bit := s.n, s.bit; bit > 2; n, bit = 1<<(bit-1)-1, bit-1 {
		for ok := true; ok; ok, _ = s.fill(n, bit) {
		}
	}
	t := time.After(7 * time.Second)
	ch := make(chan *Solver)
	go s.doRandomFill(ch)
	go s.doSomethings(ch)
	select {
	case result := <-ch:
		if result != nil {
			copy(s.line, result.line)
		}
	case <-t:
	}
}

func (s *Solver) doRandomFill(result chan *Solver) {
	ch := time.After(6 * time.Second)
outer:
	for {
		select {
		case <-ch:
			result <- (*Solver)(nil)
			return
		default:
		}
		t := s.Clone()
		for n, bit := t.n, t.bit; bit > 0; n, bit = 1<<(bit-1)-1, bit-1 {
			for {
				ok, err := t.fill(n, bit)
				if err != nil {
					continue outer
				}
				if !ok {
					break
				}
			}
			if err := t.randomFill(n, bit); err != nil {
				continue outer
			}
		}
		result <- t
		break
	}
}

func (s *Solver) doSomethings(result chan *Solver) {
	ch := time.After(6 * time.Second)
	for {
		t := s.Clone()
		if err := t.somethings(); err == nil {
			result <- t
			return
		}
		select {
		case <-ch:
			result <- t
			return
		default:
		}
	}
}

type Ints interface {
	Get(i int) int
}

type ZeroInts struct{}

func (z ZeroInts) Get(i int) int {
	return 0
}

type IntSlice []int

func (s IntSlice) Get(i int) int {
	return s[i]
}

func (s *Solver) scan(n int, bit uint) (position [][]int) {
	position = make([][]int, 1<<bit, 1<<bit)
	v := 0
	u := 0
	for i, c := range s.code {
		v = (v<<1 + int(c-'0')) & (1<<bit - 1)
		u = (u<<1 + s.used[i]) & (1<<bit - 1)
		if u == 0 && v >= (1<<(bit-1)) && v <= n {
			if i+1 == len(s.code) || s.code[i+1] == '1' {
				position[v] = append(position[v], i-int(bit-1))
			}
		}
	}
	return
}

var (
	errFillNotFound = Errorf("ErrFillNotFound")
	errFillConflict = Errorf("ErrFillConflict")
)

func (s *Solver) fill(n int, bit uint) (bool, error) {
	position := s.scan(n, bit)
	found := false
	for v := 1 << (bit - 1); v <= n; v++ {
		if len(position[v]) != 1 || s.found[v] {
			if !s.found[v] && len(position[v]) == 0 {
				return false, errFillNotFound
			}
			continue
		}
		found = true
		s.found[v] = true
		p := position[v][0]
		s.line[p] = v
		for i := 0; i < int(bit); i++ {
			if s.used[p+i] != 0 {
				return false, errFillConflict
			}
			s.used[p+i] = 1
		}
	}
	return found, nil
}

func (s *Solver) randomFill(n int, bit uint) error {
	position := s.scan(n, bit)
	indexes := perm0(n + 1)[1<<(bit-1):]
	sort.Slice(indexes, func(i, j int) bool {
		return len(position[indexes[i]]) < len(position[indexes[j]])
	})
	for _, v := range indexes {
		if s.found[v] {
			continue
		}
		if len(position[v]) == 0 {
			return errFillNotFound
		}
		m := rand.Intn(len(position[v]))
		found := false
	outer:
		for i := range position[v] {
			k := (i + m) % len(position[v])
			p := position[v][k]
			for _, u := range s.used[p : p+int(bit)] {
				if u != 0 {
					continue outer
				}
			}
			found = true
			s.found[v] = true
			s.line[p] = v
			for i := 0; i < int(bit); i++ {
				s.used[p+i] = 1
			}
			break
		}
		if !found {
			return errFillConflict
		}
	}
	return nil
}

var (
	errSomethingsInvalid = Errorf("ErrSomethingsInvalid")
	errSomethingsTimeout = Errorf("ErrSomethingsTimeout")
)

const DEBUG_SOMETHINGS = false

func (s *Solver) somethings() error {

	var index []int
	if DEBUG_SOMETHINGS {
		index = make([]int, len(s.code), len(s.code))
		for i := range index {
			index[i] = i % 10
		}
	}

	counts := make([]int, int(s.bit)+1, int(s.bit)+1)
	for i := 1; i <= s.n; i++ {
		if !s.found[i] {
			counts[bits.Len(uint(i))]++
		}
	}
	if DEBUG_SOMETHINGS {
		Println(counts)
		Println(s.line)
	}

	used := make([]int, len(s.code), len(s.code))

	// make initial positions
	position := make([][]int, 1<<s.bit, 1<<s.bit)
	{
		var v, u int
		for i, c := range s.code {
			v = (v<<1 + int(c-'0')) & (1<<s.bit - 1)
			u = (u<<1 + s.used[i]) & (1<<s.bit - 1)
			if u == 0 && v >= (1<<(s.bit-1)) && v <= s.n && !s.found[v] {
				if i+1 == len(s.code) || s.code[i+1] == '1' {
					position[v] = append(position[v], i-int(s.bit-1))
				}
			}
		}
	}

	pq := make(PriorityQueue, 0, s.n)
	for v := 1 << (s.bit - 1); v <= s.n; v++ {
		if s.found[v] || len(position[v]) == 0 {
			continue
		}
		random := rand.Intn(64)
		item := &Item{
			value:    v,
			random:   random,
			priority: len(position[v])*64 + random,
		}
		pq = append(pq, item)
	}
	heap.Init(&pq)

	ch := time.After(3 * time.Second)

	for {
		select {
		case <-ch:
			return errSomethingsTimeout
		default:
		}
		n, bit := s.n, s.bit
		for bit > 0 && counts[int(bit)] == 0 {
			n = 1<<(bit-1) - 1
			bit--
		}
		if bit == 0 {
			break
		}
		if bit < s.bit {
			for i := 1 << (bit - 1); i <= n; i++ {
				position[i] = nil
			}
			var v, u int
			for i, c := range s.code {
				v = (v<<1 + int(c-'0')) & (1<<bit - 1)
				u = (u<<1 + s.used[i] | used[i]) & (1<<bit - 1)
				if u == 0 && v >= (1<<(bit-1)) && v <= n && !s.found[v] {
					if i+1 == len(s.code) || s.code[i+1] == '1' {
						position[v] = append(position[v], i-int(bit-1))
					}
				}
			}
			for i := 1 << (bit - 1); i <= n; i++ {
				if s.found[i] {
					continue
				}
				random := rand.Intn(64)
				item := &Item{
					value:    i,
					random:   random,
					priority: len(position[i])*64 + random,
				}
				heap.Push(&pq, item)
			}
		}

		for pq.Len() > 0 {
			select {
			case <-ch:
				return errSomethingsTimeout
			default:
			}
			item := heap.Pop(&pq).(*Item)
			v := item.value.(int)
			bit = uint(bits.Len(uint(v)))
			found, breakable := false, -1
			for i := range position[v] {
				k := (i + item.random) % len(position[v])
				p := position[v][k]
				u := 0
				for b := 0; b < int(bit); b++ {
					u += used[p+b]
				}
				if u != 0 {
					breakable = p
					continue
				}
				found = true
				counts[int(bit)]--
				s.found[v] = true
				s.line[p] = v
				for b := 0; b < int(bit); b++ {
					used[p+b] = 1
				}
				if DEBUG_SOMETHINGS {
					Println("FOUND", v, bit, counts, p)
					Println(s.line)
					Println(used)
					Println(index)
				}
				break
			}
			if found {
				continue
			}
			if breakable < 0 {
				rp := rand.Intn(len(s.code))
				vv, uu := 0, 0
				for i := rp; i < len(s.code); i++ {
					vv = (vv<<1 + int(s.code[i]-'0')) & (1<<bit - 1)
					uu = (uu<<1 + s.used[i]) & (1<<bit - 1)
					if uu == 0 && v == vv {
						if i+1 == len(s.code) || s.code[i+1] == '1' {
							breakable = i - int(bit-1)
							break
						}
					}
				}
				if breakable < 0 {
					vv, uu = 0, 0
					for i := 0; i < rp; i++ {
						vv = (vv<<1 + int(s.code[i]-'0')) & (1<<bit - 1)
						uu = (uu<<1 + s.used[i]) & (1<<bit - 1)
						if uu == 0 && v == vv {
							if i+1 == len(s.code) || s.code[i+1] == '1' {
								breakable = i - int(bit-1)
								break
							}
						}
					}
				}
				if breakable < 0 {
					return errSomethingsInvalid
				}
			}
			bp := breakable
			if s.line[bp] == 0 && used[bp] != 0 {
				for b := 0; b < int(s.bit) && bp-b >= 0; b++ {
					if zv := s.line[bp-b]; zv == 0 {
						continue
					} else {
						zbit := bits.Len(uint(zv))
						for zb := 0; zb < int(zbit); zb++ {
							used[bp-b+zb] = 0
						}
						counts[zbit]++
						s.found[zv] = false
						s.line[bp-b] = 0
						random := rand.Intn(64)
						item := &Item{
							value:    zv,
							random:   random,
							priority: len(position[zv]) + random,
						}
						heap.Push(&pq, item)
						if zbit < int(s.bit) {
							position[zv] = nil
						}
						if DEBUG_SOMETHINGS {
							Println("REVERT", zv, zbit, counts, bp-b)
							Println(s.line)
							Println(used)
							Println(index)
						}
						break
					}
				}
			}
			for b := 0; b < int(bit); b++ {
				if zv := s.line[bp+b]; zv == 0 {
					continue
				} else {
					zbit := bits.Len(uint(zv))
					for zb := 0; zb < int(zbit); zb++ {
						used[bp+b+zb] = 0
					}
					counts[zbit]++
					s.found[zv] = false
					s.line[bp+b] = 0
					random := rand.Intn(64)
					item := &Item{
						value:    zv,
						random:   random,
						priority: len(position[zv]) + random,
					}
					heap.Push(&pq, item)
					if zbit < int(s.bit) {
						position[zv] = nil
					}
					if DEBUG_SOMETHINGS {
						Println("revert", zv, zbit, counts, bp+b)
						Println(s.line)
						Println(used)
						Println(index)
					}
				}
			}
			counts[int(bit)]--
			s.found[v] = true
			s.line[bp] = v
			for b := 0; b < int(bit); b++ {
				used[bp+b] = 1
			}
			if DEBUG_SOMETHINGS {
				Println("found", v, bit, counts, bp)
				Println(s.line)
				Println(used)
				Println(index)
			}
		}
	}
	return nil
}

type Item struct {
	value    any
	random   int
	priority int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x any) {
	item := x.(*Item)
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	*pq = old[:n-1]
	return item
}

func (s *Solver) analyze() {
	table := make([][]int, s.n+1, s.n+1)
	for i, c := range s.code {
		if c == '0' {
			continue
		}
		v := 0
		for b := 0; b < int(s.bit) && i+b < len(s.code); b++ {
			v = (v << 1) + int(s.code[i+b]-'0')
			if v <= s.n && (i+b+1 == len(s.code) || s.code[i+b+1] == '1') {
				table[v] = append(table[v], i)
			}
		}
	}
	result := make([][]int, 100, 100)
	for v, ps := range table {
		if len(ps) < len(result) {
			result[len(ps)] = append(result[len(ps)], v)
		}
	}
	for i, vs := range result {
		if len(vs) < 20 {
			Println("(", i, ",", len(vs), ")", vs)
		} else {
			Println("(", i, ",", len(vs), ")")
		}
	}
	indexes := perm0(s.n + 1)
	sort.Slice(indexes, func(i, j int) bool {
		return len(table[indexes[i]]) > len(table[indexes[j]])
	})
	for _, idx := range indexes[:100] {
		if len(table[idx]) < 20 {
			Println(idx, len(table[idx]), table[idx])
		} else {
			Println(idx, len(table[idx]))
		}
	}

}

func (s *Solver) scanscan() (posP, posN [][]int, prsv []int) {
	posP = make([][]int, len(s.code), len(s.code))
	posN = make([][]int, s.n+1, s.n+1)
	prsv = make([]int, len(s.code), len(s.code))
	for i := len(s.code) - 1; i >= 0; i-- {
		if s.code[i] == '0' {
			continue
		}
		v, u := 0, 0
		for b := 0; b < int(s.bit) && i+b < len(s.code); b++ {
			v = v<<1 + int(s.code[i+b]-'0')
			u = u<<1 + s.used[i+b]
			if u == 0 && v <= s.n && !s.found[v] &&
				(i+b+1 == len(s.code) || s.used[i+b+1] == 1 ||
					(s.code[i+b+1] == '1' && len(posP[i+b+1]) > 0)) {
				posP[i] = append(posP[i], v)
				posN[v] = append(posN[v], i)
				for k := i; k <= i+b; k++ {
					prsv[k]++
				}
			}
		}
	}
	return
}

func (s *Solver) fillfill() {
	for {
		posP, posN, prsv := s.scanscan()
		found := false
		for i, vs := range posP {
			// Println("P=", i, "(", prsv[i] ,")", len(vs), vs)
			if len(vs) == 1 && prsv[i] == 1 {
				v := vs[0]
				if !s.found[v] {
					bit := bits.Len(uint(v))
					s.found[v] = true
					s.line[i] = v
					for k := i; k < i+bit; k++ {
						s.used[k] = 1
					}
					found = true
				}
			}
		}
		// Println(s.used)
		// Println(s.line)
		for v, ps := range posN {
			// Println("V=", v, len(ps), ps)
			if len(ps) == 1 && !s.found[v] {
				p := ps[0]
				bit := bits.Len(uint(v))
				s.found[v] = true
				s.line[p] = v
				for k := p; k < p+bit; k++ {
					s.used[k] = 1
				}
				found = true
			}
		}
		// Println(s.used)
		// Println(s.line)
		if !found {
			break
		}
	}
}