結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-10-25 14:27:28 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 752 ms / 1,000 ms |
コード長 | 9,915 bytes |
コンパイル時間 | 12,268 ms |
コンパイル使用メモリ | 245,488 KB |
実行使用メモリ | 26,864 KB |
スコア | 29,917,268 |
最終ジャッジ日時 | 2024-10-25 14:28:18 |
合計ジャッジ時間 | 47,231 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}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 = 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)for i := 0; i < N; i++ {if best.flag&(1<<uint(i)) != 0 {pp = append(pp, i)}}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}}}