結果

問題 No.1743 Permutation Code
ユーザー ID 21712
提出日時 2024-10-18 15:49:49
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 4,722 bytes
コンパイル時間 20,044 ms
コンパイル使用メモリ 229,468 KB
実行使用メモリ 74,348 KB
最終ジャッジ日時 2024-10-18 15:52:50
合計ジャッジ時間 175,438 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import (
	. "fmt"
	"math/rand"
	"sort"
	"time"
)

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))
	result := encrypto(ans)
	if 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() {
	for n, bit := s.n, s.bit; bit > s.bit-2; n, bit = 1<<(bit-1)-1, bit-1 {
		for ok := true; ok; ok, _ = s.fill(n, bit) {
		}
	}
	ch := time.After(6 * time.Second)
outer:
	for {
		select {
		case <-ch:
			break outer
		default:
		}
		t := s.Clone()
		for n, bit := t.n, t.bit; bit > 0; n, bit = 1<<(bit-1)-1, bit-1 {
			if err := t.randomFill(n, bit); err != nil {
				continue outer
			}
			for {
				ok, err := t.fill(n, bit)
				if err != nil {
					continue outer
				}
				if !ok {
					break
				}
			}
		}
		copy(s.line, t.line)
		break
	}

}

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 {
			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
}
0