結果
| 問題 |
No.1743 Permutation Code
|
| ユーザー |
 ID 21712
|
| 提出日時 | 2024-10-20 15:04:23 |
| 言語 | Go (1.23.4) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 7 WA * 19 TLE * 3 -- * 1 |
ソースコード
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
}
}
}