結果
問題 | No.1988 Divisor Tiling |
ユーザー |
|
提出日時 | 2022-06-26 18:23:12 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 14 ms / 2,000 ms |
コード長 | 1,906 bytes |
コンパイル時間 | 11,750 ms |
コンパイル使用メモリ | 239,532 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-17 05:24:57 |
合計ジャッジ時間 | 12,300 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 32 |
ソースコード
package mainimport ("bufio""errors""fmt""os""sort""strconv")var sc = bufio.NewScanner(os.Stdin)var out = bufio.NewWriter(os.Stdout)func divide(x int) []int {m := make(map[int]struct{})for i := 1; i*i <= x; i++ {if x%i == 0 {m[i] = struct{}{}m[x/i] = struct{}{}}}var res []intfor k := range m {res = append(res, k)}sort.Ints(res)return res}func solve(n, h int) ([][]int, error) {w := n / hvar needRotate boolif w < h {h, w = w, hneedRotate = true}div := divide(n)//fmt.Println(div)f := make([][]int, h)for i := 0; i < h; i++ {f[i] = make([]int, w)}cur := 0idx := len(div) - 2for div[idx] >= w && idx >= 0 {if div[idx]%w != 0 {return nil, errors.New("Can not construct.")}nc := cur + div[idx]/wfor i := cur; i < nc; i++ {for j := 0; j < w; j++ {f[i][j] = div[idx]}}cur = ncidx--}//j := 0for idx >= 0 {v, cnt := div[idx], div[idx]for cnt > 0 {f[cur][j] = vcnt--j++}idx--}if !needRotate {return f, nil}ans := make([][]int, w)for i := 0; i < w; i++ {ans[i] = make([]int, h)}for i := 0; i < h; i++ {for j := 0; j < w; j++ {ans[j][i] = f[i][j]}}return ans, nil}func main() {buf := make([]byte, 1024*1024)sc.Buffer(buf, bufio.MaxScanTokenSize)sc.Split(bufio.ScanWords)n, h := nextInt(), nextInt()ans, err := solve(n, h)if err != nil {PrintInt(-1)return}PrintVertically(ans)}func nextInt() int {sc.Scan()i, _ := strconv.Atoi(sc.Text())return i}func PrintInt(x int) {defer out.Flush()fmt.Fprintln(out, x)}func PrintHorizonaly(x []int) {defer out.Flush()fmt.Fprintf(out, "%d", x[0])for i := 1; i < len(x); i++ {fmt.Fprintf(out, " %d", x[i])}fmt.Fprintln(out)}func PrintVertically(x [][]int) {defer out.Flush()for _, v := range x {PrintHorizonaly(v)}}