結果

問題 No.5002 stick xor
ユーザー fmhr
提出日時 2018-05-30 23:15:45
言語 Go
(1.23.4)
結果
AC  
実行時間 4 ms / 1,000 ms
コード長 5,860 bytes
コンパイル時間 4,121 ms
実行使用メモリ 1,224 KB
スコア 19
最終ジャッジ日時 2018-05-30 23:15:50
ジャッジサーバーID
（参考情報） 		judge7 /
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
    "bufio"
    "fmt"
    "log"
    "math"
    "math/rand"
    "os"
    "sort"
    "strconv"
    "time"
)
// const abcd = "abcdefghijklmnopqrstuvwxyz"
// const ABCD = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
var dx = [...]int{0, 1, 1, 1, 0, -1, -1, -1, 0}
var dy = [...]int{1, 1, 0, -1, -1, -1, 0, 1, 0}
var inf = math.MaxInt64
// var mod = 1000000007
var next = newScanner()
// ---------------------------------------------------------
func init() {
    log.SetFlags(log.Lshortfile)
    rand.Seed(time.Now().UnixNano())
}
const white = '0'
const black = '1'
// TODO
// lengthをsortして小さいものからつかう
// このとき操作順に影響されないようにする
// 重ならないように,縦か横に固定する、または操作回数を記録する
// 0 or 1 なので操作順は関係ないかも？
// 理想的なのはすべての黒を白にする よって重ならない
// そのときの操作回数は十分か？
// 1~25 * 50 = 12.5 * 500 = 6250
// 60 * 60 = 3600:
func delta(pos [4]int, f *[60][60]bool, change bool) int {
    w := 0
    b := 0
    if pos[0] > pos[2] || pos[1] > pos[3] {
        pos[0], pos[2] = pos[2], pos[0]
        pos[1], pos[3] = pos[3], pos[1]
    }
    if pos[0] == pos[2] {
        for i := pos[1]; i < pos[3]; i++ {
            if f[pos[0]][i] {
                w++
            } else {
                b++
            }
            if change {
                f[i][pos[0]] = f[i][pos[0]] == false
            }
        }
    }
    if pos[1] == pos[3] {
        for i := pos[0]; i < pos[2]; i++ {
            if f[i][pos[0]] {
                w++
            } else {
                b++
            }
            if change {
                f[i][pos[0]] = f[i][pos[0]] == false
            }
        }
    }
    return b - w
}
func solver(in []string, length []int) (rtn [][4]int) {
    log.Println(in)
    rtn = make([][4]int, 500)
    sortLens := make([]int, len(length))
    copy(sortLens, length)
    sort.Ints(sortLens)
    var f [60][60]bool
    for i := 0; i < 60; i++ {
        for j := 0; j < 60; j++ {
            switch in[i][j] {
            case white:
                f[i][j] = true
            case black:
                f[i][j] = false
            }
        }
    }
    for i := 0; i < 500; i++ {
        l := 60 - length[i] - 1
        for {
            rtn[i][0] = rand.Intn(l) + 1
            rtn[i][1] = rand.Intn(l) + 1
            rtn[i][2] = rtn[i][0]
            rtn[i][3] = rtn[i][1]
            rtn[i][2+rand.Intn(2)] += length[i] - 1
            // log.Println(i, delta(rtn[i], &f, false), rtn[i])
            if delta(rtn[i], &f, false) >= 0 {
                delta(rtn[i], &f, true)
                break
            }
        }
    }
    return rtn
}
func main() {
    n := next.Int()
    k := next.Int()
    l := next.Ints(k)
    log.Println(n, k, l)
    a := make([]string, n)
    for i := 0; i < n; i++ {
        a[i] = next.String()
    }
    rtn := solver(a, l)
    for i := 0; i < k; i++ {
        fmt.Println(rtn[i][0], rtn[i][1], rtn[i][2], rtn[i][3])
    }
}
// ---------------------------------------------------------
// Pair is...
type Pair struct {
    a, b int
}
// Pairs is sorted by []Pair struct
type Pairs []Pair
func (p Pairs) Len() int {
    return len(p)
}
func (p Pairs) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}
func (p Pairs) Less(i, j int) bool {
    return p[i].b < p[i].b
}
// func (p Pairs) Less(i, j int) bool {
//  if p[i].a < p[j].a {
//      return true
//  } else if p[i].a == p[j].a {
//      return p[i].b < p[j].b
//  }
//  return false
// }
// ------int method-------------------------
func in(c, a, z int) bool {
    return c >= a && c < z
}
func out(c, a, z int) bool {
    return !in(c, a, z)
}
func btoi(b bool) int {
    if b {
        return 1
    }
    return 0
}
func itob(a int) bool {
    return a != 0
}
func max(a ...int) int {
    r := a[0]
    for i := 0; i < len(a); i++ {
        if r < a[i] {
            r = a[i]
        }
    }
    return r
}
func min(a ...int) int {
    r := a[0]
    for i := 0; i < len(a); i++ {
        if r > a[i] {
            r = a[i]
        }
    }
    return r
}
func sum(a []int) (r int) {
    for i := range a {
        r += a[i]
    }
    return r
}
func pro(a []int) int {
    r := a[0]
    for i := 1; i < len(a); i++ {
        r *= a[i]
    }
    return r
}
func fill(a []int, n int) []int {
    for i := range a {
        a[i] = n
    }
    return a
}
func minmax(a, b int) (int, int) {
    if a > b {
        return b, a
    }
    return a, b
}
// func abs(a int) int {
//  if a < 0 {
//      return -a
//  }
//  return a
// }
func abs(a int) int {
    mask := a >> 63
    return (a ^ mask) - mask
}
func ceil(a, b int) int {
    if a%b != 0 {
        return 1
    }
    return 0
}
func printStrings(out []string) {
    for i := range out {
        fmt.Print(out[i])
        if i != len(out)-1 {
            fmt.Print(" ")
        }
    }
    fmt.Print("\n")
}
func printInts(out []int) {
    for i := range out {
        fmt.Print(out[i])
        if i != len(out)-1 {
            fmt.Print(" ")
        }
    }
    fmt.Print("\n")
}
// ---------- buffered scanner -----------------------------------------
type scanner struct {
    r   *bufio.Reader
    buf []byte
    p   int
}
func newScanner() *scanner {
    rdr := bufio.NewReaderSize(os.Stdin, 10000)
    return &scanner{r: rdr}
}
func (s *scanner) next() string {
    s.pre()
    start := s.p
    for ; s.p < len(s.buf); s.p++ {
        if s.buf[s.p] == ' ' {
            break
        }
    }
    result := string(s.buf[start:s.p])
    s.p++
    return result
}
func (s *scanner) Line() string {
    s.pre()
    start := s.p
    s.p = len(s.buf)
    return string(s.buf[start:])
}
func (s *scanner) String() string {
    return s.next()
}
func (s *scanner) Int() int {
    v, err := strconv.Atoi(s.next())
    if err != nil {
        log.Fatal(err)
    }
    return v
}
func (s *scanner) Ints(n int) []int {
    r := make([]int, n)
    for i := 0; i < n; i++ {
        r[i] = s.Int()
    }
    return r
}
func (s *scanner) Int64() int64 {
    v, err := strconv.ParseInt(s.next(), 10, 64)
    if err != nil {
        log.Fatal(err)
    }
    return v
}
func (s *scanner) Uint64() uint64 {
    v, err := strconv.ParseUint(s.next(), 10, 64)
    if err != nil {
        log.Fatal(err)
    }
    return v
}
func (s *scanner) Float64() float64 {
    v, err := strconv.ParseFloat(s.next(), 64)
    if err != nil {
        log.Fatal(err)
    }
    return v
}
func (s *scanner) pre() {
    if s.p >= len(s.buf) {
        s.readLine()
        s.p = 0
    }
}
func (s *scanner) readLine() {
    s.buf = make([]byte, 0)
    for {
        l, p, err := s.r.ReadLine()
        if err != nil {
            log.Fatal(err)
        }
        s.buf = append(s.buf, l...)
        if !p {
            break
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0