結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-10-27 18:13:45 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 773 ms / 1,000 ms |
コード長 | 18,511 bytes |
コンパイル時間 | 11,986 ms |
コンパイル使用メモリ | 223,084 KB |
実行使用メモリ | 7,916 KB |
スコア | 39,805,912 |
最終ジャッジ日時 | 2024-10-27 18:14:39 |
合計ジャッジ時間 | 52,986 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
package mainimport (. "fmt""math""math/rand". "sort""time")func main() {var input stringScan(&input)if input == "LOCAL" {runLocal()return}if input == "MULTI" {runMulti()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)}func calc(n int, a, b []int64, u, v []int) (a0, b0 int64) {ta := make([]int64, n, n)tb := make([]int64, n, n)copy(ta, a)copy(tb, b)for i, ui := range u {vi := v[i]aa := (ta[ui] + ta[vi]) / 2bb := (tb[ui] + tb[vi]) / 2ta[ui], tb[ui] = aa, bbta[vi], tb[vi] = aa, bb}a0, b0 = ta[0], tb[0]return}func runMulti() {var test int = 10var seed int64 = SeedScan(&test, &seed)var total int64for t := 0; t < test; t, seed = t+1, seed^abs(seed*1717+int64(t)) {Printf("Test %2d/%2d: Seed = %20d, ", t+1, test, seed)a, b := generate(N, seed)start := time.Now()s := NewSolver(N, a, b)s.Solve()u, v := s.Answer()end := time.Since(start)Printf("%v, %s\n", end, s.info)if err := check(N, u, v); err != nil {if err != errZeroIndexed {Println(err)panic(err)}}a0, b0 := calc(N, a, b, u, v)va, vb := abs(a0-Base), abs(b0-Base)score := int64(2e6) - int64(1e5*math.Log10(float64(max(va, vb)+1)))if max(va, vb) == 0 {score += X - int64(len(u))}total += scorePrintf(" SCORE = %7d, max(Va,Vb) = %18d, len = %2d\n",score, max(va, vb), len(Sprint(max(va, vb))))}Printf("TOTAL SCORE = %9d ( estimated 50 cases = %10d )\n",total, total*50/int64(test))}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}s.info = "tree"s.tree()}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 = 1e4)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 {bestii := -1bestiiScore := score(best) / int64(best.c)var bestiiState *Statefor ii := 1; ii < len(pp); ii++ {w := pp[ii]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)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) < bestiiScore {bestii = iibestiiScore = max(wsa, wsb) / int64(best.c)bestiiState = best2}}if bestii > 0 {ppp := []int{}for i := 0; i < N; i++ {if bestiiState.flag&(1<<uint(i)) != 0 {ppp = append(ppp, i)}}pp[bestii] = ppp[0]for p := 1; p < bestiiState.c; p *= 2 {for i := 0; i < bestiiState.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}}}func (s *Solver) tree() {trees := [][]int{}limit := X - len(s.u) - 1var take func(depth, inner, leaf int, nodes []int)take = func(depth, inner, leaf int, nodes []int) {if depth == 0 {nodes[0] = 1take(depth+1, 0, 1, nodes)nodes[0] = 0return}if leaf > N {return}if inner <= limit {t := make([]int, depth)copy(t, nodes[:depth])trees = append(trees, t)}if depth == len(nodes) {return}nodes[depth] = 0for i := 0; i < nodes[depth-1]; i++ {nodes[depth] += 2inner--leaf += 2take(depth+1, inner, leaf, nodes)}nodes[depth] = 0}const MaxDepth = 10take(0, 0, 0, make([]int, MaxDepth))// Println("Tree = ", len(trees))bestScore := max(abs(s.a[0]-Base), abs(s.b[0]-Base))bestCs := make([]int64, N)bestPs := make([]int, N)cs := make([]int64, N)ps := rand.Perm(N)for _, tree := range trees {var ncnt inttcs := cs[:0]for i, c := range tree {if i+1 < len(tree) {c -= tree[i+1] / 2}ncnt += cfor ; c > 0; c-- {tcs = append(tcs, 1<<uint(i))}}// Println(tree)// Println(nc, cs[:ncnt])for i, p := range ps {if p == 0 && i >= ncnt {ps[0], ps[i] = 0, ps[0]break}}var va, vb int64for i, t := range tcs {p := ps[i]va += s.a[p] / tvb += s.b[p] / t}score := max(abs(va-Base), abs(vb-Base))for li := 0; li < ncnt; li++ {lp, lt := ps[li], tcs[li]tempVa, tempVb, tempScore := va, vb, scoretempRi := -1for ri := li + 1; ri < N; ri++ {if lp == 0 && ri >= ncnt {break}rp := ps[ri]tva := va - s.a[lp]/lt + s.a[rp]/lttvb := vb - s.b[lp]/lt + s.b[rp]/ltif ri < ncnt {rt := tcs[ri]tva += s.a[lp]/rt - s.a[rp]/rttvb += s.b[lp]/rt - s.b[rp]/rt}temp := max(abs(tva-Base), abs(tvb-Base))if temp < tempScore {tempVa, tempVb, tempScore = tva, tvb, temptempRi = ri}}if tempRi >= 0 {va, vb, score = tempVa, tempVb, tempScoreps[li], ps[tempRi] = ps[tempRi], ps[li]}}if score < bestScore {bestScore = scorebestCs = bestCs[:ncnt]copy(bestCs, tcs)bestPs = bestPs[:ncnt]copy(bestPs, ps)}}{ps, cs := bestPs[:], bestCs[:]for i := 0; i < N; i++ {found := falsefor _, p := range ps {if i == p {found = truebreak}}if !found {ps = append(ps, i)}}var va, vb int64for i, c := range cs {p := ps[i]va += s.a[p] / cvb += s.b[p] / c}score := bestScorefor {updated := falsefor li := 0; li < len(cs); li++ {lp, lt := ps[li], cs[li]tempRi, tempVa, tempVb, tempScore := -1, va, vb, scorefor ri := li + 1; ri < N; ri++ {if lp == 0 && ri >= len(cs) {break}rp := ps[ri]tva := va - s.a[lp]/lt + s.a[rp]/lttvb := vb - s.b[lp]/lt + s.b[rp]/ltif ri < len(cs) {rt := cs[ri]tva += s.a[lp]/rt - s.a[rp]/rttvb += s.b[lp]/rt - s.b[rp]/rt}temp := max(abs(tva-Base), abs(tvb-Base))if temp < tempScore {tempRi, tempVa, tempVb, tempScore = ri, tva, tvb, temp}}if tempRi >= 0 {va, vb, score = tempVa, tempVb, tempScoreps[li], ps[tempRi] = ps[tempRi], ps[li]updated = true}}if !updated {bestScore = scorebreak}}}// Println(bestScore, len(Sprint(bestScore)))// Println(bestPs)// Println(bestCs)for {var maxC int64 // = slices.Max(bestCs)for _, c := range bestCs {if c > maxC {maxC = c}}if maxC < 2 {break}another := -1for i, c := range bestCs {if c != maxC {continue}if another < 0 {another = i} else {p1, p2 := bestPs[i], bestPs[another]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, bbif p1 < p2 {bestCs[i] /= 2bestCs[another] = 0} else {bestCs[i] = 0bestCs[another] /= 2}another = -1}}}}