fork download
copy 
  1. package main
  2.  
  3. import ("fmt"
  4. 		"bufio"
  5. 		"os"
  6.  
  7. )
  8.  
  9. func solveOne(s string) int64 {
  10. 	n := len(s)
  11. 	if n == 0 {
  12. 		return 0
  13. 	}
  14.  
  15. 	hasOne := false
  16. 	for i := 0; i < n; i++ {
  17. 		if s[i] == '1' {
  18. 			hasOne = true
  19. 			break
  20. 		}
  21. 	}
  22. 	if !hasOne {
  23. 		return 0
  24. 	}
  25.  
  26. 	ss := s + s
  27. 	best, cur := 0, 0
  28. 	for i := 0; i < 2*n; i++ {
  29. 		if ss[i] == '1' {
  30. 			cur++
  31. 			if cur > n {
  32. 				cur = n
  33. 			}
  34. 			if cur > best {
  35. 				best = cur
  36. 			}
  37. 		} else {
  38. 			cur = 0
  39. 		}
  40. 	}
  41.  
  42. 	if best >= n {
  43. 		return int64(n) * int64(n)
  44. 	}
  45.  
  46. 	sum := best + 1
  47. 	a := sum / 2
  48. 	b := sum - a
  49. 	return int64(a) * int64(b)
  50. }
  51.  
  52. func main() {
  53. 	in := bufio.NewReaderSize(os.Stdin, 1<<20)
  54. 	out := bufio.NewWriterSize(os.Stdout, 1<<20)
  55. 	defer out.Flush()
  56.  
  57. 	var t int
  58. 	fmt.Fscan(in, &t)
  59. 	for ; t > 0; t-- {
  60. 		var s string
  61. 		fmt.Fscan(in, &s)
  62. 		fmt.Fprintln(out, solveOne(s))
  63. 	}
  64. }
  65.  
Success #stdin #stdout 0s 5640KB
comments (?)
stdin
copy 
5
0
1
011
11011
01101
stdout
copy 
0
1
2
6
2
https://ideone.com/gasuFO
language:
Go (go 1.12.1)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!