結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-10-24 15:42:54 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 410 ms / 1,000 ms |
コード長 | 7,867 bytes |
コンパイル時間 | 11,969 ms |
コンパイル使用メモリ | 227,536 KB |
実行使用メモリ | 8,384 KB |
スコア | 35,073,581 |
最終ジャッジ日時 | 2024-10-24 15:43:30 |
合計ジャッジ時間 | 34,233 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
package mainimport (. "fmt""math""math/rand""time")func main() {var input stringScan(&input)if input == "LOCAL" {runLocal()return}var n intSscan(input, &n)a := make([]int64, n, n)b := make([]int64, n, n)for i := range a {Scan(&a[i], &b[i])}s := NewSolver(n, a, b)s.Solve()u, v := s.Answer()if err := check(n, u, v); err != nil {if err == errZeroIndexed {fixIndex(u, v)} else {Println(err)panic(err)}}output(u, v)}func output(u, v []int) {Println(len(u))for i, ui := range u {Println(ui, v[i])}}func fixIndex(u, v []int) {isZeroIndexed := falsefor i, ui := range u {if ui == 0 || v[i] == 0 {isZeroIndexed = truebreak}}if isZeroIndexed {for i := range u {u[i]++v[i]++}}}const (N = 45ABmax = int64(1e18)ABmin = int64(1e17)X = 50Base = int64(5e17)Seed = 12121212)func generate(n int, seed int64) (a, b []int64) {a = make([]int64, n, n)b = make([]int64, n, n)r := rand.New(rand.NewSource(seed))for i := range a {a[i] = r.Int63n(ABmax-ABmin) + ABmin}for i := range b {b[i] = r.Int63n(ABmax-ABmin) + ABmin}return}var errZeroIndexed = Errorf("ErrZeroIndexed")func check(n int, u, v []int) error {if len(u) != len(v) {return Errorf("<<<WA>>> len(u)=%d != len(v)=%d ", len(u), len(v))}if len(u) > X {return Errorf("<<<WA>>> len(u) > %d", len(u), X)}if len(u) == 0 {return nil}min, max := n, 0for i, ui := range u {if ui == v[i] {return Errorf("<<<WA>>> u[%d]=%d == v[%d]=%d", i, ui, i, v[i])}if ui < min {min = ui}if v[i] < min {min = v[i]}if ui > max {max = ui}if v[i] > max {max = v[i]}}if !((min == 0 && max < n) || (min == 1 && max <= n)) {return Errorf("<<<WA>>> min(u,v)=%d, max(u,v)=%d", min, max)}if min == 0 {return errZeroIndexed}return nil}func show(n int, a, b []int64) {Println("N =", n)for i, ai := range a {Printf("A[%2d] = %19d, B[%2d] = %19d\n", i, ai, i, b[i])}}func abs(a int64) int64 {if a < 0 {return -a}return a}func max(a, b int64) int64 {if a < b {return b}return a}func min(a, b int64) int64 {if a < b {return a}return b}func process(n int, a, b []int64, u, v []int) {ta := make([]int64, n, n)tb := make([]int64, n, n)copy(ta, a)copy(tb, b)a, b = nil, nilPrintln("Len = ", len(u))for i, ui := range u {vi := v[i]Printf("u[%2d] = %2d, v[%2d] = %2d\n", i, ui, i, vi)Printf(" A[%2d] = %19d, B[%2d] = %19d\n", ui, ta[ui], ui, tb[ui])Printf(" A[%2d] = %19d, B[%2d] = %19d\n", vi, ta[vi], vi, tb[vi])aa, bb := (ta[ui]+ta[vi])/2, (tb[ui]+tb[vi])/2Printf(" A[**] = %19d, B[**] = %19d\n", aa, bb)da, db := abs(aa-Base), abs(bb-Base)Printf(" diff = %19d, diff = %19d\n", da, db)Printf(" max = %19d, len = %2d\n", max(da, db), len(Sprint(max(da, db))))ta[ui], tb[ui] = aa, bbta[vi], tb[vi] = aa, bb}va, vb := abs(ta[0]-Base), abs(tb[0]-Base)Printf("V(A) = %19d, V(B) = %19d\n", va, vb)Printf(" max = %19d, len = %2d\n", max(va, vb), len(Sprint(max(va, vb))))score := int64(2e6) - int64(1e5*math.Log10(float64(max(va, vb)+1)))if max(va, vb) == 0 {score += X - int64(len(u))}Printf("SCORE = %7d, SCORE*50 = %9d\n", score, score*50)}func runLocal() {var n int = Nvar seed int64 = SeedScan(&n, &seed)a, b := generate(n, seed)show(n, a, b)t := time.Now()s := NewSolver(n, a, b)s.Solve()u, v := s.Answer()Println(time.Since(t))Println(s.info)if err := check(n, u, v); err != nil {if err != errZeroIndexed {Println(err)panic(err)}}process(n, a, b, u, v)}type Solver struct {n inta, b []int64u, v []intinfo string}func NewSolver(n int, a, b []int64) *Solver {ta := make([]int64, n, n)tb := make([]int64, n, n)copy(ta, a)copy(tb, b)return &Solver{n, ta, tb, []int{}, []int{}, ""}}func (s *Solver) Clone() *Solver {ta := make([]int64, s.n, s.n)tb := make([]int64, s.n, s.n)copy(ta, s.a)copy(tb, s.b)return &Solver{s.n, ta, tb, []int{}, []int{}, ""}}func (s *Solver) Answer() (u, v []int) {return s.u, s.v}func (s *Solver) score() int64 {return max(abs(s.a[0]-Base), abs(s.b[0]-Base))}func (s *Solver) Solve() {if s.n != N {s.greedy()return}g := s.Clone()g.info = "greedy"g.greedy()var best *Solver = gfor p := 4; p <= 32; p *= 2 {t := s.Clone()t.info = Sprint("greedy&average(", p, ")")if !t.greedy() || len(s.u)+p+1 >= X {continue}if err := t.average(p); err != nil {continue}if t.greedy() {t.info += "&greedy"}if t.score() < best.score() {best = t}}for p := 4; p <= 32; p *= 2 {for i := 0; i < 100; i++ {t := s.Clone()t.info = Sprint("avarage(", p, ")")t.average(p)if t.greedy() {t.info += "&greedy"}if t.score() < best.score() {best = t}}}for p := 4; p <= 32; p *= 2 {for sz := 10; sz+p < X-2; sz++ {for i := 0; i < 100; i++ {t := s.Clone()t.info = Sprint("random(", sz, ")&avarage(", p, ")")t.random(sz)if err := t.average(p); err != nil {continue}if t.greedy() {t.info += "&greedy"}if t.score() < best.score() {best = t}}}}for sz := 15; sz < X; sz++ {for i := 0; i < 2000; i++ {t := s.Clone()t.info = Sprint("random(", sz, ")")t.random(sz)if t.greedy() {t.info += "&greedy"}if t.score() < best.score() {best = t}}}s.info = best.infos.u, s.v = best.u, best.v}func (s *Solver) greedy() bool {before := len(s.u)for i := len(s.u); i < X; i++ {best := s.score()zk := -1for k := 1; k < s.n; k++ {aa := (s.a[0] + s.a[k]) / 2bb := (s.b[0] + s.b[k]) / 2s := max(abs(aa-Base), abs(bb-Base))if s < best {best, zk = s, k}}if zk < 0 {break}s.u = append(s.u, 0)s.v = append(s.v, zk)aa := (s.a[0] + s.a[zk]) / 2bb := (s.b[0] + s.b[zk]) / 2s.a[0], s.b[0] = aa, bbs.a[zk], s.b[zk] = aa, bb}return before != len(s.u)}// size .. 2,4,8,16,32func (s *Solver) average(size int) error {switch size {default:return Errorf("wrong size %d", size)case 2, 4, 8, 16, 32:if len(s.u)+size+1 >= X {return Errorf("over")}}const Div = 100target := (Base / Div) * int64(size)idx := rand.Perm(N)for i, x := range idx {if x == 0 {idx[0], idx[i] = idx[i], idx[0]break}}var sumA, sumB int64for _, i := range idx[:size] {sumA += s.a[i] / DivsumB += s.b[i] / Div}best := max(abs(sumA-target), abs(sumB-target))for {update := 0for i := 1; i < size; i++ {ii := idx[i]sumA -= s.a[ii] / DivsumB -= s.b[ii] / Divxk := -1for k := size; k < N; k++ {ik := idx[k]sumA += s.a[ik] / DivsumB += s.b[ik] / Divv := max(abs(sumA-target), abs(sumB-target))if v < best {best, xk = v, k}sumA -= s.a[ik] / DivsumB -= s.b[ik] / Div}if xk < 0 {sumA += s.a[ii] / DivsumB += s.b[ii] / Div} else {ik := idx[xk]sumA += s.a[ik] / DivsumB += s.b[ik] / Dividx[i], idx[xk] = ik, iiupdate++}}if update == 0 {break}}for p := 1; p < size; p *= 2 {for i := 0; i < size; i += p * 2 {ii, ip := idx[i], idx[i+p]s.u = append(s.u, ii)s.v = append(s.v, ip)aa := (s.a[ii] + s.a[ip]) / 2bb := (s.b[ii] + s.b[ip]) / 2s.a[ii], s.b[ii] = aa, bbs.a[ip], s.b[ip] = aa, bb}}return nil}func (s *Solver) random(size int) {for ; size > 0; size-- {x := rand.Intn(s.n)y := (x + rand.Intn(s.n-1) + 1) % s.ns.u = append(s.u, x)s.v = append(s.v, y)aa := (s.a[x] + s.a[y]) / 2bb := (s.b[x] + s.b[y]) / 2s.a[x], s.b[x] = aa, bbs.a[y], s.b[y] = aa, bb}}