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 } } }