#1021426 (Go) No.1743 Permutation Code

提出ソース

結果

問題	No.1743 Permutation Code
ユーザー	ID 21712
提出日時	2024-10-20 18:32:48
言語	Go (1.22.1)
結果	WA
実行時間	-
コード長	5,946 bytes
コンパイル時間	11,214 ms
コンパイル使用メモリ	218,836 KB
実行使用メモリ	289,240 KB
最終ジャッジ日時	2024-10-20 18:35:58
合計ジャッジ時間	181,873 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	28 ms 6,816 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	WA	-
testcase_27	WA	-
testcase_28	TLE	-
testcase_29	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

import (
	. "fmt"
	"math/bits"
	"math/rand"
	"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))
	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.fillfill()
}

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 := 0
		for b := 0; b < int(s.bit) && i+b < len(s.code); b++ {
			v = v<<1 + int(s.code[i+b]-'0')
			if s.used[i+b] != 0 {
				break
			}
			if 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() {
	ch := time.After(7 * time.Second)
	var pos [][]int
	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 {
			pos = posN
			break
		}
	}
	values := perm0(s.n + 1)[1:]
	rand.Shuffle(len(values), func(i, j int) {
		values[i], values[j] = values[j], values[i]
	})
	used := make([]int, len(s.code), len(s.code))
	for _, v := range values {
		if s.found[v] {
			continue
		}
		bit := bits.Len(uint(v))
		r := rand.Intn(len(pos[v]))
		for i := range pos[v] {
			p := pos[v][(i+r)%len(pos[v])]
			u := 0
			for b := 0; b < bit; b++ {
				u += s.used[p+b] + used[p+b]
			}
			if u != 0 {
				continue
			}
			s.found[v] = true
			s.line[p] = v
			for b := 0; b < bit; b++ {
				used[p+b] = 1
			}
			break
		}
	}
	for {
		count := 0
		for _, v := range values {
			select {
			case <-ch:
				return
			default:
			}
			if s.found[v] {
				continue
			}
			count++
			bit := bits.Len(uint(v))
			r := rand.Intn(len(pos[v]))
			found, breakable := false, -1
			for i := range pos[v] {
				p := pos[v][(i+r)%len(pos[v])]
				u1, u2 := 0, 0
				for b := 0; b < bit; b++ {
					u1 += s.used[p+b]
					u2 += used[p+b]
				}
				if u1 != 0 {
					continue
				}
				if u2 != 0 {
					breakable = p
					continue
				}
				s.found[v] = true
				s.line[p] = v
				for b := 0; b < bit; b++ {
					used[p+b] = 1
				}
				found = true
				break
			}
			if found || breakable < 0 {
				continue
			}
			bp := breakable
			if s.line[bp] == 0 && used[bp] != 0 {
				for b := 0; b < int(s.bit); b++ {
					if s.line[bp-b] == 0 {
						continue
					}
					zv := s.line[bp-b]
					zbit := bits.Len(uint(zv))
					s.found[zv] = false
					s.line[bp-b] = 0
					for zb := 0; zb < zbit; zb++ {
						used[bp-b+zb] = 0
					}
					break
				}
			}
			for b := 0; b < bit; b++ {
				if s.line[bp+b] == 0 {
					continue
				}
				zv := s.line[bp+b]
				zbit := bits.Len(uint(zv))
				s.found[zv] = false
				s.line[bp+b] = 0
				for zb := 0; zb < zbit; zb++ {
					used[bp+b+zb] = 0
				}
			}
			s.found[v] = true
			s.line[bp] = v
			for b := 0; b < bit; b++ {
				used[bp+b] = 1
			}
		}
		if count == 0 {
			break
		}
	}
}

yukicoder

結果

テストケース

ソースコード