結果

問題 No.2986 Permutation Puzzle
ユーザー ID 21712ID 21712
提出日時 2024-11-30 12:55:16
言語 Go
(1.22.1)
結果
WA  
実行時間 -
コード長 8,356 bytes
コンパイル時間 11,918 ms
コンパイル使用メモリ 220,128 KB
実行使用メモリ 8,096 KB
最終ジャッジ日時 2024-12-02 12:32:59
合計ジャッジ時間 12,829 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
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 AC 5 ms
6,820 KB
testcase_21 AC 3 ms
6,816 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 38 ms
8,088 KB
testcase_26 WA -
testcase_27 AC 12 ms
7,960 KB
testcase_28 AC 45 ms
8,092 KB
testcase_29 WA -
testcase_30 AC 45 ms
8,092 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 AC 42 ms
8,088 KB
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 AC 47 ms
8,088 KB
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 31 ms
8,092 KB
testcase_42 WA -
testcase_43 AC 62 ms
8,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder - ProblemID 11672 - special judge checker
package main

import . "fmt"
import . "io"
import "os"
import "math/rand"

func sample1(p *Problem) (ans []int) {
	p.n, p.k = 4, 3
	p.a = NewPPuzzle(p.n)
	p.a.f = [][]int{
		[]int{4, 1, 3, 2},
		[]int{2, 4, 1, 3},
		[]int{3, 2, 4, 1},
		[]int{1, 3, 2, 4},
	}
	p.b = p.a.Clone()
	p.b.OperateCol(3)
	p.b.OperateRow(4)
	p.b.OperateRow(4)

	ans = []int{5, 4}
	return
}

func sample2(p *Problem) (ans []int) {
	p.n, p.k = 4, 3
	p.a = NewPPuzzle(p.n)
	p.a.f = [][]int{
		[]int{4, 1, 3, 2},
		[]int{2, 4, 1, 3},
		[]int{3, 2, 4, 1},
		[]int{1, 3, 2, 4},
	}
	p.b = p.a.Clone()
	p.b.OperateRow(2)
	p.b.OperateRow(4)
	p.b.OperateRow(3)

	ans = []int{5}
	return
}

func sample3(p *Problem) (ans []int) {
	n, k := 7, 2
	seed := int64(987654323456789)
	rng := rand.New(rand.NewSource(seed))
	t := NewProblem(rng, n, k)
	*p = *t
	ans = []int{12, 12, 6, 5, 6}
	return
}

func sample4(p *Problem) (ans []int) {
	n, k := 10, 4
	seed := int64(2024 * 1225 * 2024 * 1225)
	rng := rand.New(rand.NewSource(seed))
	t := NewProblem(rng, n, k)
	*p = *t
	ans = []int{12, 14, 18, 17, 13, 4, 4, 4, 4, 4, 11, 20, 17, 13, 13, 19, 15, 13, 19}
	return
}

func isSample(p *Problem) (ans []int, ok bool) {
	seed := int64(1)
	rng := rand.New(rand.NewSource(seed))
	t := NewProblem(rng, p.n, p.k)
	switch {
	case p.n == 4 && p.k == 3:
		ans = sample1(t)
		if p.IsSame(t) {
			return ans, true
		}
		ans = sample2(t)
		if p.IsSame(t) {
			return ans, true
		}
	case p.n == 7 && p.k == 2:
		ans = sample3(t)
		if p.IsSame(t) {
			return ans, true
		}
	case p.n == 10 && p.k == 4:
		ans = sample4(t)
		if p.IsSame(t) {
			return ans, true
		}
	}
	return nil, false
}

func main() {
	p := ScanProblem(os.Stdin)

	if ans, ok := isSample(p); ok {
		showAnswer(p.n, ans)
		return
	}

	if checkWA(p) {
		return
	}

	sol := solve(p)

	for i := 1; i <= p.n*2; i++ {
		var ss []int
		if i <= p.n {
			ss = p.b.SelectCol(i)
		} else {
			ss = p.b.SelectRow(i - p.n)
		}
		cnt := cycle(ss)
		if cnt > 0 && (1000-len(sol))%cnt == 0 {
			// too large
			zz := p.b.Clone()
			sel := (i-1)%p.n + 1
			tmp := []int{}
			for len(tmp)+len(sol) < 1000 {
				tmp = append(tmp, sel)
				if i <= p.n {
					zz.OperateCol(sel)
				} else {
					zz.OperateRow(sel)
				}
				sel = ss[sel-1]
			}
			if p.b.IsSame(zz) {
				sol = append(tmp, sol...)
				showAnswer(p.n, sol)
				return
			}
		}
	}

}

func checkWA(p *Problem) bool {
	tn := (p.n-4)*3 + (p.k - 2) + 1
	switch tn {
	case 1:
		// no output
	case 2:
		// not found M
		Println("H")
	case 3:
		// wrong M
		Println(0)
	case 4:
		// wrong M
		Println(1001)
	case 5:
		// too many values at 1st-line
		Println(1, 2)
	case 6:
		// not found 2-line
		Println(3)
	case 7:
		// not found X[0]
		Println(3)
		Println(" ")
	case 8:
		// wrong X[0]
		Println(3)
		Println("W A")
	case 9:
		// wrong X[0]
		Println(3)
		Println("WWWWWW AAAAA")
	case 10:
		// not found P[0]
		Println(3)
		Println("R")
	case 11:
		// not found P[0]
		Println(3)
		Println("R XXX")
	case 12:
		// wrong P[0]
		Println(3)
		Println("R", 0)
	case 13:
		// wrong P[0]
		Println(3)
		Println("C", p.n+1)
	case 14:
		// too many values at 2-line
		Println(3)
		Println("C", 1, 2)
	case 15:
		// not found 3-line
		Println(3)
		Println("R 1")
	case 16:
		// Wrong Answer
		Println(1)
		Println("R 1")
	default:
		return false
	}
	return true
}

func showAnswer(n int, ans []int) {
	Println(len(ans))
	for _, s := range ans {
		if s <= n {
			Println("C", s)
		} else {
			Println("R", s-n)
		}
	}
}

type Problem struct {
	n, k int
	a, b *PPuzzle
}

func NewProblem(r *rand.Rand, n, k int) *Problem {
	a := NewPPuzzle(n)
	a.Init()
	a.shuffle(r, 1000)
	b := a.Clone()
	for {
		for i := 0; i < k; i++ {
			x := r.Intn(n+n) + 1
			if x <= n {
				b.OperateCol(x)
			} else {
				b.OperateRow(x - n)
			}
		}
		if !a.IsSame(b) {
			break
		}
		b = a.Clone()
	}
	return &Problem{n, k, a, b}
}

func ScanProblem(rd Reader) *Problem {
	var n, k int
	Fscan(rd, &n, &k)
	a := ScanPPuzzle(rd, n)
	b := ScanPPuzzle(rd, n)
	return &Problem{n, k, a, b}
}

func (p *Problem) IsSame(t *Problem) bool {
	return p.n == t.n &&
		p.k == t.k &&
		p.a.IsSame(t.a) &&
		p.b.IsSame(t.b)
}

func (p *Problem) Show() {
	Println(p.n, p.k)
	p.a.Show()
	p.b.Show()
}

type PPuzzle struct {
	n          int
	f          [][]int
	iCol, iRow []int
}

func NewPPuzzle(n int) *PPuzzle {
	f := make([][]int, n)
	iCol := make([]int, n)
	iRow := make([]int, n)
	for i := range f {
		f[i] = make([]int, n)
		iCol[i] = i
		iRow[i] = i
	}
	return &PPuzzle{n, f, iCol, iRow}
}

func ScanPPuzzle(rd Reader, n int) *PPuzzle {
	f := make([][]int, n)
	iCol := make([]int, n)
	iRow := make([]int, n)
	for i := range f {
		f[i] = make([]int, n)
		for j := range f[i] {
			Fscan(rd, &f[i][j])
		}
		iCol[i] = i
		iRow[i] = i
	}
	return &PPuzzle{n, f, iCol, iRow}
}

// r, c ... 1-indexed
func (p *PPuzzle) Get(r, c int) int {
	return p.f[p.iRow[r-1]][p.iCol[c-1]]
}

func (p *PPuzzle) Init() {
	for i, row := range p.f {
		for k := range row {
			row[k] = (k+i)%p.n + 1
		}
	}
}

// c1, c2 ... 1-indexed
func (p *PPuzzle) swapCol(c1, c2 int) {
	c1--
	c2--
	for _, row := range p.f {
		row[c1], row[c2] = row[c2], row[c1]
	}
}

// r1, r2 ... 1-indexed
func (p *PPuzzle) swapRow(r1, r2 int) {
	r1--
	r2--
	p.f[r1], p.f[r2] = p.f[r2], p.f[r1]
}

func (p *PPuzzle) shuffle(r *rand.Rand, s int) {
	for ; s > 0; s-- {
		e := r.Intn(p.n) + 1
		w := (e+r.Intn(p.n-1)+1)%p.n + 1
		if s%2 == 0 {
			p.swapCol(e, w)
		} else {
			p.swapRow(e, w)
		}
	}
}

// c ... 1-indexed
func (p *PPuzzle) SelectCol(c int) []int {
	z := make([]int, p.n)
	for i := range z {
		z[i] = p.Get(i+1, c)
	}
	return z
}

// r ... 1-indexed
func (p *PPuzzle) SelectRow(r int) []int {
	z := make([]int, p.n)
	for i := range z {
		z[i] = p.Get(r, i+1)
	}
	return z
}

// c ... 1-indexed
func (p *PPuzzle) OperateCol(c int) {
	z := p.SelectCol(c)
	tmp := make([]int, p.n)
	for i, v := range p.iCol {
		tmp[z[i]-1] = v
	}
	p.iCol = tmp
}

// r ... 1-indexed
func (p *PPuzzle) OperateRow(r int) {
	z := p.SelectRow(r)
	tmp := make([]int, p.n)
	for i, v := range p.iRow {
		tmp[z[i]-1] = v
	}
	p.iRow = tmp
}

func (p *PPuzzle) Clone() *PPuzzle {
	iCol := make([]int, p.n)
	iRow := make([]int, p.n)
	copy(iCol, p.iCol)
	copy(iRow, p.iRow)
	return &PPuzzle{p.n, p.f, iCol, iRow}
}

func (p *PPuzzle) IsSame(t *PPuzzle) bool {
	for r := 1; r <= p.n; r++ {
		for c := 1; c <= p.n; c++ {
			if p.Get(r, c) != t.Get(r, c) {
				return false
			}
		}
	}
	return true
}

func (p *PPuzzle) Show() {
	for r, row := range p.f {
		for c := range row {
			if c > 0 {
				Print(" ")
			}
			Print(p.Get(r+1, c+1))
		}
		Println()
	}
}

func debugln(args ...interface{}) {
	// Println(args...)
}

func solve(p *Problem) (sol []int) {

	_, m := search(p.k, p.a, p.b, nil)
	x := p.a.Clone()
	for _, s := range m {
		if s <= p.n {
			x.OperateCol(s)
		} else {
			x.OperateRow(s - p.n)
		}
	}

	type PS struct {
		s int
		p *PPuzzle
	}

	y := p.a.Clone()
	pp := []*PS{}
	for _, s := range m {
		pp = append(pp, &PS{s, y.Clone()})
		if s <= p.n {
			y.OperateCol(s)
		} else {
			y.OperateRow(s - p.n)
		}
	}

	sol = []int{}
	for i := range pp {
		ps := pp[len(pp)-i-1]
		var sp []int
		sel := ps.s
		if ps.s <= p.n {
			sp = ps.p.SelectCol(ps.s)
		} else {
			sp = ps.p.SelectRow(ps.s - p.n)
			sel -= p.n
		}
		cc := cycle(sp)
		sel = sp[sel-1]
		for k := 0; k < cc-1; k++ {
			if ps.s <= p.n {
				sol = append(sol, sel)
			} else {
				sol = append(sol, sel+p.n)
			}
			sel = sp[sel-1]
		}
	}

	z := p.b.Clone()
	for i, sel := range sol {
		if sel <= p.n {
			z.OperateCol(sel)
		} else {
			z.OperateRow(sel - p.n)
		}
		if p.a.IsSame(z) {
			sol = sol[:i+1]
			break
		}
	}

	return
}

func cycle(p []int) int {
	z := make([]int, len(p))
	t := make([]int, len(p))
	copy(z, p)
	for c := 0; ; c++ {
		ok := true
		for i, k := range p {
			t[k-1] = z[i]
			ok = ok && t[k-1] == p[k-1]
		}
		t, z = z, t
		if ok {
			return c + 1
		}
	}
}

func search(s int, p, t *PPuzzle, r []int) (bool, []int) {
	if s == 0 {
		if t.IsSame(p) {
			return true, r
		} else {
			return false, nil
		}
	}
	for i := 1; i <= p.n*2; i++ {
		x := p.Clone()
		r = append(r, i)
		if i <= p.n {
			x.OperateCol(i)
		} else {
			x.OperateRow(i - p.n)
		}
		if ok, rr := search(s-1, x, t, r); ok {
			return true, rr
		}
		r = r[:len(r)-1]
	}
	return false, nil
}
0