結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2024-11-30 11:36:11
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 5,914 bytes
コンパイル時間 11,780 ms
コンパイル使用メモリ 232,112 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-02 12:32:22
合計ジャッジ時間 13,599 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other WA * 40
権限があれば一括ダウンロードができます

ソースコード

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
	}

	// too large answer
	Println(1000)
	for i := 0; i < 1000; i++ {
		Println("C 1")
	}
}

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:
		// not found P[0]
		Println(3)
		Println("R")
	case 9:
		// wrong P[0]
		Println(3)
		Println("R", 0)
	case 10:
		// wrong P[0]
		Println(3)
		Println("C", p.n+1)
	case 11:
		// not found 3-line
		Println(3)
		Println("R 1")
	case 12:
		// 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()
	}
}
0