結果
| 問題 | No.5020 Averaging |
| ユーザー |
 ID 21712
|
| 提出日時 | 2024-10-28 12:24:02 |
| 言語 | Go (1.22.1) |
| 結果 |
AC
|
| 実行時間 | 764 ms / 1,000 ms |
| コード長 | 29,401 bytes |
| コンパイル時間 | 11,612 ms |
| コンパイル使用メモリ | 232,768 KB |
| 実行使用メモリ | 6,820 KB |
| スコア | 69,503,322 |
| 最終ジャッジ日時 | 2024-10-28 12:24:55 |
| 合計ジャッジ時間 | 51,889 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
| 純コード判定しない問題か言語 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 734 ms
6,816 KB |
| testcase_01 | AC | 753 ms
6,820 KB |
| testcase_02 | AC | 721 ms
6,816 KB |
| testcase_03 | AC | 746 ms
6,820 KB |
| testcase_04 | AC | 714 ms
6,816 KB |
| testcase_05 | AC | 735 ms
6,816 KB |
| testcase_06 | AC | 754 ms
6,816 KB |
| testcase_07 | AC | 731 ms
6,820 KB |
| testcase_08 | AC | 756 ms
6,816 KB |
| testcase_09 | AC | 720 ms
6,816 KB |
| testcase_10 | AC | 753 ms
6,820 KB |
| testcase_11 | AC | 730 ms
6,820 KB |
| testcase_12 | AC | 735 ms
6,820 KB |
| testcase_13 | AC | 751 ms
6,820 KB |
| testcase_14 | AC | 728 ms
6,820 KB |
| testcase_15 | AC | 751 ms
6,816 KB |
| testcase_16 | AC | 725 ms
6,820 KB |
| testcase_17 | AC | 734 ms
6,820 KB |
| testcase_18 | AC | 725 ms
6,820 KB |
| testcase_19 | AC | 728 ms
6,816 KB |
| testcase_20 | AC | 758 ms
6,820 KB |
| testcase_21 | AC | 726 ms
6,820 KB |
| testcase_22 | AC | 764 ms
6,820 KB |
| testcase_23 | AC | 728 ms
6,816 KB |
| testcase_24 | AC | 742 ms
6,820 KB |
| testcase_25 | AC | 723 ms
6,820 KB |
| testcase_26 | AC | 724 ms
6,820 KB |
| testcase_27 | AC | 743 ms
6,820 KB |
| testcase_28 | AC | 727 ms
6,816 KB |
| testcase_29 | AC | 746 ms
6,816 KB |
| testcase_30 | AC | 728 ms
6,820 KB |
| testcase_31 | AC | 732 ms
6,816 KB |
| testcase_32 | AC | 742 ms
6,816 KB |
| testcase_33 | AC | 724 ms
6,816 KB |
| testcase_34 | AC | 755 ms
6,816 KB |
| testcase_35 | AC | 713 ms
6,816 KB |
| testcase_36 | AC | 747 ms
6,820 KB |
| testcase_37 | AC | 714 ms
6,816 KB |
| testcase_38 | AC | 733 ms
6,820 KB |
| testcase_39 | AC | 728 ms
6,820 KB |
| testcase_40 | AC | 729 ms
6,816 KB |
| testcase_41 | AC | 747 ms
6,816 KB |
| testcase_42 | AC | 716 ms
6,820 KB |
| testcase_43 | AC | 737 ms
6,820 KB |
| testcase_44 | AC | 727 ms
6,816 KB |
| testcase_45 | AC | 727 ms
6,816 KB |
| testcase_46 | AC | 752 ms
6,816 KB |
| testcase_47 | AC | 730 ms
6,820 KB |
| testcase_48 | AC | 753 ms
6,820 KB |
| testcase_49 | AC | 716 ms
6,816 KB |
ソースコード
package main
import (
. "fmt"
"math"
"math/rand"
. "sort"
"time"
)
func main() {
var input string
Scan(&input)
if input == "LOCAL" {
runLocal()
return
}
if input == "MULTI" {
runMulti()
return
}
var n int
Sscan(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 := false
for i, ui := range u {
if ui == 0 || v[i] == 0 {
isZeroIndexed = true
break
}
}
if isZeroIndexed {
for i := range u {
u[i]++
v[i]++
}
}
}
const (
N = 45
ABmax = int64(1e18)
ABmin = int64(1e17)
X = 50
Base = 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, 0
for 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, nil
Println("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])/2
Printf(" 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, bb
ta[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 = N
var seed int64 = Seed
Scan(&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]) / 2
bb := (tb[ui] + tb[vi]) / 2
ta[ui], tb[ui] = aa, bb
ta[vi], tb[vi] = aa, bb
}
a0, b0 = ta[0], tb[0]
return
}
func runMulti() {
var test int = 10
var seed int64 = Seed
Scan(&test, &seed)
var total int64
for 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 += score
Printf(" 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 int
a, b []int64
u, v []int
info 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
}
best := s
for i := 0; i < 10; i++ {
t := s.Clone()
t.info = Sprint("walk [", i, "]")
t.walk()
if t.score() < best.score() {
best = t
}
}
s.info = best.info
s.u, s.v = best.u, best.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 := -1
for k := 1; k < s.n; k++ {
aa := (s.a[0] + s.a[k]) / 2
bb := (s.b[0] + s.b[k]) / 2
s := 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]) / 2
bb := (s.b[0] + s.b[zk]) / 2
s.a[0], s.b[0] = aa, bb
s.a[zk], s.b[zk] = aa, bb
}
return before != len(s.u)
}
// size .. 2,4,8,16,32
func (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 = 100
target := (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 int64
for _, i := range idx[:size] {
sumA += s.a[i] / Div
sumB += s.b[i] / Div
}
best := max(abs(sumA-target), abs(sumB-target))
for {
update := 0
for i := 1; i < size; i++ {
ii := idx[i]
sumA -= s.a[ii] / Div
sumB -= s.b[ii] / Div
xk := -1
for k := size; k < N; k++ {
ik := idx[k]
sumA += s.a[ik] / Div
sumB += s.b[ik] / Div
v := max(abs(sumA-target), abs(sumB-target))
if v < best {
best, xk = v, k
}
sumA -= s.a[ik] / Div
sumB -= s.b[ik] / Div
}
if xk < 0 {
sumA += s.a[ii] / Div
sumB += s.b[ii] / Div
} else {
ik := idx[xk]
sumA += s.a[ik] / Div
sumB += s.b[ik] / Div
idx[i], idx[xk] = ik, ii
update++
}
}
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]) / 2
bb := (s.b[ii] + s.b[ip]) / 2
s.a[ii], s.b[ii] = aa, bb
s.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.n
s.u = append(s.u, x)
s.v = append(s.v, y)
aa := (s.a[x] + s.a[y]) / 2
bb := (s.b[x] + s.b[y]) / 2
s.a[x], s.b[x] = aa, bb
s.a[y], s.b[y] = aa, bb
}
}
func (s *Solver) dp() {
const (
Div = 100
Vmax = 1e4
)
type State struct {
c int
flag, 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)] = first
for 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 := 32
for len(s.u)+b2+best.c+1 >= 45 {
b2 /= 2
}
if b2 >= 2 {
bestii := -1
bestiiScore := score(best) / int64(best.c)
var bestiiState *State
for ii := 1; ii < len(pp); ii++ {
w := pp[ii]
wa := best.sumA - s.a[w]/Div
wb := best.sumB - s.b[w]/Div
baseA := 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 = ii
bestiiScore = 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]) / 2
bb := (s.b[p1] + s.b[p2]) / 2
s.a[p1], s.b[p1] = aa, bb
s.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]) / 2
bb := (s.b[p1] + s.b[p2]) / 2
s.a[p1], s.b[p1] = aa, bb
s.a[p2], s.b[p2] = aa, bb
}
}
}
func (s *Solver) tree() {
trees := [][]int{}
limit := X - len(s.u) - 1
var take func(depth, inner, leaf int, nodes []int)
take = func(depth, inner, leaf int, nodes []int) {
if depth == 0 {
nodes[0] = 1
take(depth+1, 0, 1, nodes)
nodes[0] = 0
return
}
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] = 0
for i := 0; i < nodes[depth-1]; i++ {
nodes[depth] += 2
inner--
leaf += 2
take(depth+1, inner, leaf, nodes)
}
nodes[depth] = 0
}
const MaxDepth = 10
take(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 int
tcs := cs[:0]
for i, c := range tree {
if i+1 < len(tree) {
c -= tree[i+1] / 2
}
ncnt += c
for ; 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 int64
for i, t := range tcs {
p := ps[i]
va += s.a[p] / t
vb += 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, score
tempRi := -1
for ri := li + 1; ri < N; ri++ {
if lp == 0 && ri >= ncnt {
break
}
rp := ps[ri]
tva := va - s.a[lp]/lt + s.a[rp]/lt
tvb := vb - s.b[lp]/lt + s.b[rp]/lt
if ri < ncnt {
rt := tcs[ri]
tva += s.a[lp]/rt - s.a[rp]/rt
tvb += s.b[lp]/rt - s.b[rp]/rt
}
temp := max(abs(tva-Base), abs(tvb-Base))
if temp < tempScore {
tempVa, tempVb, tempScore = tva, tvb, temp
tempRi = ri
}
}
if tempRi >= 0 {
va, vb, score = tempVa, tempVb, tempScore
ps[li], ps[tempRi] = ps[tempRi], ps[li]
}
}
if score < bestScore {
bestScore = score
bestCs = bestCs[:ncnt]
copy(bestCs, tcs)
bestPs = bestPs[:ncnt]
copy(bestPs, ps)
}
}
{
ps, cs := bestPs[:], bestCs[:]
for i := 0; i < N; i++ {
found := false
for _, p := range ps {
if i == p {
found = true
break
}
}
if !found {
ps = append(ps, i)
}
}
var va, vb int64
for i, c := range cs {
p := ps[i]
va += s.a[p] / c
vb += s.b[p] / c
}
score := bestScore
for {
updated := false
for li := 0; li < len(cs); li++ {
lp, lt := ps[li], cs[li]
tempRi, tempVa, tempVb, tempScore := -1, va, vb, score
for 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]/lt
tvb := vb - s.b[lp]/lt + s.b[rp]/lt
if ri < len(cs) {
rt := cs[ri]
tva += s.a[lp]/rt - s.a[rp]/rt
tvb += 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, tempScore
ps[li], ps[tempRi] = ps[tempRi], ps[li]
updated = true
}
}
if !updated {
bestScore = score
break
}
}
}
// 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 := -1
for 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]) / 2
bb := (s.b[p1] + s.b[p2]) / 2
s.a[p1], s.b[p1] = aa, bb
s.a[p2], s.b[p2] = aa, bb
if p1 < p2 {
bestCs[i] /= 2
bestCs[another] = 0
} else {
bestCs[i] = 0
bestCs[another] /= 2
}
another = -1
}
}
}
}
func (s *Solver) walk() {
ps := rand.Perm(N)
for i, p := range ps {
if p == 0 {
ps[0], ps[i] = ps[i], ps[0]
break
}
}
const C = N / 2
cs := make([]int64, 0, N)
for i := 1; i <= C; i++ {
cs = append(cs, 1<<uint(i))
}
cs = append(cs, 1<<C)
cs = cs[:N]
inner := C
leaf := C + 1
var va, vb int64
for i, c := range cs {
if c != 0 {
p := ps[i]
va += s.a[p] / c
vb += s.b[p] / c
}
}
score := max(abs(va-Base), abs(vb-Base))
hs := make([]int, N, N)
gs := make([]int, 0, N)
for i, c := range cs {
if c != 0 {
hs[i] = len(gs)
gs = append(gs, i)
} else {
hs[i] = -1
}
}
// Println("-- START --")
// Println("inner:", inner, ", leaf:", leaf)
// Println("hs:", hs)
// Println("gs:", gs)
// Println("ps:", ps)
// Println("cs:", cs)
// Printf("Va: %18d, Vb: %18d, Score: %18d, Len: %2d\n", va, vb, score, len(Sprint(score)))
// Println("----------")
hasBest := false
bestScore := score
bestPs := make([]int, N, N)
copy(bestPs, ps)
bestCs := make([]int64, N, N)
const WW = 500000
const Changed = 50
const NoChanged = 1
const NoChangesLimit = 1000
const KickSize = 100
const Kick = 1
nochanges, kicks := 0, 0
for ww := 0; ww < WW; ww++ {
if nochanges > NoChangesLimit {
// Printf("[%07d] Kick\n", ww)
nochanges = 0
kicks = KickSize
if !hasBest || score < bestScore {
bestScore = score
copy(bestPs, ps)
copy(bestCs, cs)
hasBest = true
}
}
lgi := rand.Intn(len(gs))
li := gs[lgi]
ri := (li + rand.Intn(N-1) + 1) % N
lp, rp := ps[li], ps[ri]
lc, rc := cs[li], cs[ri]
switch {
case lc > 0 && rc > 0 && lc == rc && lp == 0 && rp != 0:
// Merge
{
tva1 := va - s.a[lp]/lc - s.a[rp]/rc + s.a[lp]/(lc/2)
tvb1 := vb - s.b[lp]/lc - s.b[rp]/rc + s.b[lp]/(lc/2)
tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
if tscore1 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Merge: %2d %2d -> %d (%d -> %d)\n", ww, lp, rp, lp, lc, lc/2)
cs[li], cs[ri] = lc/2, 0
va, vb, score = tva1, tvb1, tscore1
rgi := hs[ri]
gs[rgi] = gs[len(gs)-1]
hs[gs[rgi]] = rgi
gs = gs[:len(gs)-1]
hs[ri] = -1
inner--
leaf--
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
}
case lc > 0 && rc > 0 && lc == rc && lp != 0 && rp == 0:
// Merge
{
tva2 := va - s.a[lp]/lc - s.a[rp]/rc + s.a[rp]/(rc/2)
tvb2 := vb - s.b[lp]/lc - s.b[rp]/rc + s.b[rp]/(rc/2)
tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
if tscore2 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, rp, rc, rc/2)
cs[li], cs[ri] = 0, rc/2
va, vb, score = tva2, tvb2, tscore2
gs[lgi] = gs[len(gs)-1]
hs[gs[lgi]] = lgi
gs = gs[:len(gs)-1]
hs[li] = -1
inner--
leaf--
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
}
case lc > 0 && rc > 0 && lc == rc && lp != 0 && rp != 0:
// Merge
{
tva1 := va - s.a[lp]/lc - s.a[rp]/rc + s.a[lp]/(lc/2)
tvb1 := vb - s.b[lp]/lc - s.b[rp]/rc + s.b[lp]/(lc/2)
tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
tva2 := va - s.a[lp]/lc - s.a[rp]/rc + s.a[rp]/(rc/2)
tvb2 := vb - s.b[lp]/lc - s.b[rp]/rc + s.b[rp]/(rc/2)
tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
if tscore1 <= score && tscore1 <= tscore2 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, lp, lc, lc/2)
cs[li], cs[ri] = lc/2, 0
va, vb, score = tva1, tvb1, tscore1
rgi := hs[ri]
gs[rgi] = gs[len(gs)-1]
hs[gs[rgi]] = rgi
gs = gs[:len(gs)-1]
hs[ri] = -1
inner--
leaf--
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else if tscore2 <= score && tscore2 <= tscore1 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Merge: %2d %2d -> %2d (%d -> %d)\n", ww, lp, rp, rp, rc, rc/2)
cs[li], cs[ri] = 0, rc/2
va, vb, score = tva2, tvb2, tscore2
gs[lgi] = gs[len(gs)-1]
hs[gs[lgi]] = lgi
gs = gs[:len(gs)-1]
hs[li] = -1
inner--
leaf--
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
}
case lc > 0 && rc > 0 && lc != rc:
// Swap
{
tva1 := va - s.a[lp]/lc - s.a[rp]/rc + s.a[lp]/rc + s.a[rp]/lc
tvb1 := vb - s.b[lp]/lc - s.b[rp]/rc + s.b[lp]/rc + s.b[rp]/lc
tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
if tscore1 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
va, vb, score = tva1, tvb1, tscore1
ps[li], ps[ri] = ps[ri], ps[li]
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
}
case (lc > 0 && rc == 0) && lp == 0:
// Divide
if inner+1 <= X && leaf+1 <= N {
tva2 := va - s.a[lp]/lc + s.a[lp]/(lc*2) + s.a[rp]/(lc*2)
tvb2 := vb - s.b[lp]/lc + s.b[lp]/(lc*2) + s.b[rp]/(lc*2)
tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
if tscore2 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Divide: %2d -> %2d (%d -> %d)\n", ww, lp, rp, lc, lc*2)
cs[li], cs[ri] = lc*2, lc*2
va, vb, score = tva2, tvb2, tscore2
hs[ri] = len(gs)
gs = append(gs, ri)
inner++
leaf++
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
}
case (lc > 0 && rc == 0) && lp != 0:
// Swap OR Divide
{
tva1 := va - s.a[lp]/lc + s.a[rp]/lc
tvb1 := vb - s.b[lp]/lc + s.b[rp]/lc
tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
if inner+1 <= X && leaf+1 <= N {
tva2 := va - s.a[lp]/lc + s.a[lp]/(lc*2) + s.a[rp]/(lc*2)
tvb2 := vb - s.b[lp]/lc + s.b[lp]/(lc*2) + s.b[rp]/(lc*2)
tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
if tscore1 <= score && tscore1 <= tscore2 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
va, vb, score = tva1, tvb1, tscore1
ps[li], ps[ri] = ps[ri], ps[li]
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else if tscore2 <= score && tscore2 <= tscore1 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Divide: %2d -> %2d (%d -> %d)\n", ww, lp, rp, lc, lc*2)
cs[li], cs[ri] = lc*2, lc*2
va, vb, score = tva2, tvb2, tscore2
hs[ri] = len(gs)
gs = append(gs, ri)
inner++
leaf++
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
} else if tscore1 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
va, vb, score = tva1, tvb1, tscore1
ps[li], ps[ri] = ps[ri], ps[li]
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
}
case (lc == 0 && rc > 0) && rp == 0:
// Divide
if inner+1 <= X && leaf+1 <= N {
tva2 := va - s.a[rp]/rc + s.a[lp]/(rc*2) + s.a[rp]/(rc*2)
tvb2 := vb - s.b[rp]/rc + s.b[lp]/(rc*2) + s.b[rp]/(rc*2)
tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
if tscore2 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Divide: %2d -> %2d (%d -> %d)\n", ww, rp, lp, rc, rc*2)
cs[li], cs[ri] = rc*2, rc*2
va, vb, score = tva2, tvb2, tscore2
hs[li] = len(gs)
gs = append(gs, li)
inner++
leaf++
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
}
case (lc == 0 && rc > 0) && rp != 0:
// Swap OR Divide
{
tva1 := va - s.a[lp]/lc + s.a[rp]/lc
tvb1 := vb - s.b[lp]/lc + s.b[rp]/lc
tscore1 := max(abs(tva1-Base), abs(tvb1-Base))
if inner+1 <= X && leaf+1 <= N {
tva2 := va - s.a[rp]/rc + s.a[lp]/(rc*2) + s.a[rp]/(rc*2)
tvb2 := vb - s.b[rp]/rc + s.b[lp]/(rc*2) + s.b[rp]/(rc*2)
tscore2 := max(abs(tva2-Base), abs(tvb2-Base))
if tscore1 <= score && tscore1 <= tscore2 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
va, vb, score = tva1, tvb1, tscore1
ps[li], ps[ri] = ps[ri], ps[li]
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else if tscore2 <= score && tscore2 <= tscore1 || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Divide: %2d -> %2d (%d -> %d)\n", ww, rp, lp, rc, rc*2)
cs[li], cs[ri] = rc*2, rc*2
va, vb, score = tva2, tvb2, tscore2
hs[li] = len(gs)
gs = append(gs, li)
inner++
leaf++
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
} else if tscore1 <= score || (kicks > 0 && rand.Intn(KickSize) < kicks) {
// Printf("[%07d] Swap: %2d <-> %2d (%d <-> %d)\n", ww, lp, rp, lc, rc)
va, vb, score = tva1, tvb1, tscore1
ps[li], ps[ri] = ps[ri], ps[li]
if kicks > 0 {
kicks -= Kick
} else {
nochanges -= Changed
}
} else {
nochanges += NoChanged
}
}
}
}
// Println("-- END --")
// Println("inner:", inner, ", leaf:", leaf)
// Println("hs:", hs)
// Println("gs:", gs)
// Println("ps:", ps)
// Println("cs:", cs)
// Printf("Va: %18d, Vb: %18d, Score: %18d, Len: %2d\n", va, vb, score, len(Sprint(score)))
// Println("---------")
if hasBest && bestScore < score {
// Printf("HasBest: %d -> %d\n", score, bestScore)
score = bestScore
ps = bestPs
cs = bestCs
}
for {
var maxC int64
for _, c := range cs {
maxC = max(maxC, c)
}
if maxC < 2 {
break
}
another := -1
for i, c := range cs {
if c != maxC {
continue
}
if another < 0 {
another = i
} else {
p1, p2 := ps[i], ps[another]
s.u = append(s.u, p1)
s.v = append(s.v, p2)
aa := (s.a[p1] + s.a[p2]) / 2
bb := (s.b[p1] + s.b[p2]) / 2
s.a[p1], s.b[p1] = aa, bb
s.a[p2], s.b[p2] = aa, bb
if p1 < p2 {
cs[i] /= 2
cs[another] = 0
} else {
cs[i] = 0
cs[another] /= 2
}
another = -1
}
}
}
}