結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-10-25 17:00:52 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 957 ms / 1,000 ms |
コード長 | 12,986 bytes |
コンパイル時間 | 12,194 ms |
コンパイル使用メモリ | 226,140 KB |
実行使用メモリ | 30,904 KB |
スコア | 31,111,967 |
最終ジャッジ日時 | 2024-10-25 17:01:50 |
合計ジャッジ時間 | 55,293 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
package mainimport (. "fmt""math""math/rand". "sort""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}t := s.Clone()t.dp()if t.score() < s.score() {s.u, s.v = t.u, t.v}}func (s *Solver) goodluck() *Solver {var best *Solver{g := s.Clone()g.info = "greedy"g.greedy()best = g}for 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}}}return best}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}}func (s *Solver) dp() {const (Div = 100Vmax = 1.2e4)type State struct {c intflag, sumA, sumB int64}score := func(st *State) int64 {a := abs(st.sumA - Base/Div*int64(st.c))b := abs(st.sumB - Base/Div*int64(st.c))return max(a, b)}index := func(st *State) int {return int(score(st) / (Base / Div * int64(st.c) / Vmax))}add := func(st *State, x int) *State {if st == nil {return &State{c: 1,flag: 1 << uint(x),sumA: s.a[x] / Div,sumB: s.b[x] / Div,}} else {return &State{c: st.c + 1,flag: st.flag | (1 << uint(x)),sumA: st.sumA + s.a[x]/Div,sumB: st.sumB + s.b[x]/Div,}}}better := func(st1, st2 *State) *State {if st1 == nil {return st2} else if st2 == nil {return st1} else if score(st1)/int64(st1.c) < score(st2)/int64(st2.c) {return st1} else {return st2}}dp := make([][]*State, 33)for i := range dp {dp[i] = make([]*State, Vmax+1)}first := add(nil, 0)dp[1][index(first)] = firstfor x := 1; x < N; x++ {for i := 31; i > 0; i-- {for _, e := range dp[i] {if e == nil {continue}st := add(e, x)idx := index(st)dp[i+1][idx] = better(dp[i+1][idx], st)}}}xx := []*State{}for i := 2; i <= 32; i *= 2 {for _, e := range dp[i] {if e != nil {xx = append(xx, e)}}}Slice(xx, func(i, j int) bool {return score(xx[i])/int64(xx[i].c) < score(xx[j])/int64(xx[j].c)})best := xx[0]pp := make([]int, 0, best.c)rr := make([]int, 0, N-best.c)for i := 0; i < N; i++ {if best.flag&(1<<uint(i)) != 0 {pp = append(pp, i)} else {rr = append(rr, i)}}b2 := 32for len(s.u)+b2+best.c+1 >= 45 {b2 /= 2}if b2 >= 2 {w := pp[len(pp)-1]wa := best.sumA - s.a[w]/Divwb := best.sumB - s.b[w]/DivbaseA := min((ABmax-1)/Div, max(ABmin/Div, Base/Div*int64(best.c)-wa))baseB := min((ABmax-1)/Div, max(ABmin/Div, Base/Div*int64(best.c)-wb))score2 := func(st *State) int64 {a := abs(st.sumA - baseA*int64(st.c))b := abs(st.sumB - baseB*int64(st.c))return max(a, b)}index2 := func(st *State) int {a := abs(st.sumA - baseA*int64(st.c))b := abs(st.sumB - baseB*int64(st.c))if a > b {return int(min(Base/Div, a) / (Base / Div * int64(st.c) / Vmax))} else {return int(min(Base/Div, b) / (Base / Div * int64(st.c) / Vmax))}}better2 := func(st1, st2 *State) *State {if st1 == nil {return st2} else if st2 == nil {return st1} else if score2(st1)/int64(st1.c) < score2(st2)/int64(st2.c) {return st1} else {return st2}}dp2 := make([][]*State, b2+1)for i := range dp2 {dp2[i] = make([]*State, Vmax+1)}dp2[0][0] = &State{}rr = append(rr, w)for _, r := range rr {for i := b2 - 1; i >= 0; i-- {for _, e := range dp2[i] {if e == nil {continue}st := add(e, r)idx := index2(st)if idx < 0 || idx > Vmax {Println("idx:", idx)Println(st)panic(Errorf("idx"))}dp2[i+1][idx] = better2(dp2[i+1][idx], st)}}}yy := []*State{}for i := 2; i <= b2; i *= 2 {for _, e := range dp2[i] {if e != nil {yy = append(yy, e)}}}Slice(yy, func(i, j int) bool {return score2(yy[i])/int64(yy[i].c) < score2(yy[j])/int64(yy[j].c)})best2 := yy[0]wsa := abs(wa + best2.sumA/int64(best2.c) - Base/Div*int64(best.c))wsb := abs(wb + best2.sumB/int64(best2.c) - Base/Div*int64(best.c))// Printf("expect elem A: %18d, B: %18d\n", baseA, baseB)// Printf("before elem A: %18d, B: %18d\n", s.a[w]/Div, s.b[w]/Div)// Printf("after elem A: %18d, B: %18d\n", best2.sumA/int64(best2.c), best2.sumB/int64(best2.c))// Printf("before elem diff A: %18d, B: %18d\n", abs(baseA-s.a[w]/Div), abs(baseB-s.b[w]/Div))// Printf("after elem diff A: %18d, B: %18d\n", abs(baseA-best2.sumA/int64(best2.c)), abs(baseB-best2.sumB/int64(best2.c)))// Printf("before max(Va,Vb): %19d\n", score(best)/int64(best.c))// Printf("after max(Va,Vb): %19d\n", max(wsa, wsb)/int64(best.c))if max(wsa, wsb)/int64(best.c) < score(best)/int64(best.c) {// Println("OK")ppp := []int{}for i := 0; i < N; i++ {if best2.flag&(1<<uint(i)) != 0 {ppp = append(ppp, i)}}pp[len(pp)-1] = ppp[0]for p := 1; p < best2.c; p *= 2 {for i := 0; i < best2.c; i += p * 2 {p1 := ppp[i]p2 := ppp[i+p]s.u = append(s.u, p1)s.v = append(s.v, p2)aa := (s.a[p1] + s.a[p2]) / 2bb := (s.b[p1] + s.b[p2]) / 2s.a[p1], s.b[p1] = aa, bbs.a[p2], s.b[p2] = aa, bb}}}}for p := 1; p < best.c; p *= 2 {for i := 0; i < best.c; i += p * 2 {p1 := pp[i]p2 := pp[i+p]s.u = append(s.u, p1)s.v = append(s.v, p2)aa := (s.a[p1] + s.a[p2]) / 2bb := (s.b[p1] + s.b[p2]) / 2s.a[p1], s.b[p1] = aa, bbs.a[p2], s.b[p2] = aa, bb}}}