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