// 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 := 01; i <= p.n*2; i++ { var cnt int if i <= p.n { cnt = cycle(p.b.SelectCol(i)) } else { cnt = cycle(p.b.SelectRow(i - p.n)) } if cnt > 0 && (1000-len(sol))%cnt == 0 { // too large tmp := []int{} for len(tmp)+len(sol) < 1000 { tmp = append(tmp, i) } sol = append(tmp, sol...) showAnswer(p.n, sol) break } } } 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: // not found 2-line Println(3) case 6: // not found X[0] Println(3) Println(" ") case 7: // wrong X[0] Println(3) Println("W A") case 8: // wrong X[0] Println(3) Println("WWWWWW AAAAA") case 9: // not found P[0] Println(3) Println("R") case 10: // not found P[0] Println(3) Println("R XXX") case 11: // wrong P[0] Println(3) Println("R", 0) case 12: // wrong P[0] Println(3) Println("C", p.n+1) case 13: // not found 3-line Println(3) Println("R 1") case 14: // 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] } if ok { return c + 1 } t, z = z, t } } 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 }