package main import ( . "fmt" . "os" bf "bufio" "container/list" "math" "math/rand" "sort" ) func min(a,b int) int { if ars[j]-ls[j] }) } } used := make([]bool, q) plist := list.New() loop1: for rl,tt0 := range tt { var best int64 = math.MaxInt64 var bestvg int = -1 var bestti int = -1 for vg,tt1:= range tt0 { for i, t := range tt1 { value := int64(rs[t]-ls[t]+1)*100 if value < best { best = value bestvg = vg bestti = i } } } if best < math.MaxInt64 { tt1 := tt0[bestvg] tt1[0],tt1[bestti] = tt1[bestti],tt1[0] i := tt1[0] tt[rl][bestvg] = tt1[1:] elem := plist.PushBack(i) tte[rl][bestvg] = append(tte[rl][bestvg], elem) used[i] = true break loop1 } } for _, rl := range rand.Perm(50) { for _, vg := range rand.Perm(50) { if len(tt[rl][vg]) == 0 || len(tte[rl][vg]) > 0 { continue } t := tt[rl][vg][0] elem := plist.Front() var best int64 var bestElem *list.Element { i := elem.Value.(int) best = -int64(rs[i]-ls[i]+1)*100 best += int64(rs[t]-ls[t]+1)*100 best += parttime(ls,rs,p, t, i) } for elem != nil { i := elem.Value.(int) next := elem.Next() if next != nil { k := next.Value.(int) diff := -parttime(ls,rs,p, i,k) diff += parttime(ls,rs,p, i,t) diff += parttime(ls,rs,p, t,k) if diff < best { best = diff bestElem = elem } } else { diff := parttime(ls,rs,p, i,t) if diff < best { best = diff bestElem = elem } } elem = next } if bestElem != nil { newElem := plist.InsertAfter(t, bestElem) tt[rl][vg] = tt[rl][vg][1:] tte[rl][vg] = append(tte[rl][vg], newElem) used[t] = true } else { elem = plist.Front() newElem := plist.InsertBefore(t, elem) tt[rl][vg] = tt[rl][vg][1:] tte[rl][vg] = append(tte[rl][vg], newElem) used[t] = true } } } for rl, tt0 := range tt { for vg, tt1 := range tt0 { for _, t := range tt1 { var best int64 = math.MaxInt64 var bestElem *list.Element for _, elem := range tte[rl][vg] { i := elem.Value.(int) if prev := elem.Prev(); prev != nil { j := prev.Value.(int) diff :=-parttime(ls,rs,p, j, i) diff += parttime(ls,rs,p, j, t) diff += parttime(ls,rs,p, t, i) if diff < best { best = diff bestElem = prev } } else { diff :=-int64(rs[i]-ls[i]+1)*100 diff += int64(rs[t]-ls[t]+1)*100 diff += parttime(ls,rs,p, t, i) if diff < best { best = diff bestElem = nil } } if next := elem.Next(); next != nil { j := next.Value.(int) diff :=-parttime(ls,rs,p, i, j) diff += parttime(ls,rs,p, i, t) diff += parttime(ls,rs,p, t, j) if diff < best { best = diff bestElem = elem } } else { diff := parttime(ls,rs,p, i, t) if diff < best { best = diff bestElem = elem } } } if best < math.MaxInt64 { if bestElem != nil { newElem := plist.InsertAfter(t, bestElem) tte[rl][vg] = append(tte[rl][vg], newElem) used[t] = true } else { bestElem = plist.Front() newElem := plist.InsertBefore(t, bestElem) tte[rl][vg] = append(tte[rl][vg], newElem) used[t] = true } } } } } if plist.Len() == len(p) { p = p[:0] elem := plist.Front() for elem != nil { p = append(p, elem.Value.(int)) elem = elem.Next() } } for j := 0; j < 50; j++ { for i := range rand.Perm(q) { k := min(rand.Intn(q/2500+1)+i+1,q-1) f,g := min(i,k), max(i,k) var t0,t1 int64 if f > 0 { t0 += parttime(ls,rs,p,f-1,f) t1 += parttime(ls,rs,p,f-1,g) } else { t0 += int64(rs[p[f]]-ls[p[f]]+1)*100 t1 += int64(rs[p[g]]-rs[p[g]]+1)*100 } if g+1 < len(p) { t0 += parttime(ls,rs,p,g,g+1) t1 += parttime(ls,rs,p,f,g+1) } if t0 >= t1 { for ; f= len(p) { continue } var t0 int64 if i>0 { t0 += parttime(ls,rs,p,i-1,i) } else { t0 += int64(rs[p[i]]-ls[p[i]]+1)*100 } for j:=0;j < PS; j++ { if i+j+1 < len(p) { t0 += parttime(ls,rs,p, i+j,i+j+1) } } var orig [PS]int copy(orig[:], p[i:i+PS]) var bestpmi int = -1 for pmi, pm := range perm4 { var t1 int64 for j,pv := range pm { p[i+pv] = orig[j] } if i>0 { t1 += parttime(ls,rs,p,i-1,i) } else { t1 += int64(rs[p[i]]-ls[p[i]]+1)*100 } for j:=0;j= 0 { pm := perm4[bestpmi] for j,pv := range pm { p[i+pv] = orig[j] } } else { copy(p[i:i+PS],orig[:]) } } } for i,vp := range p { if i > 0 { Fprint(wr, " ") } Fprint(wr, vp+1) } Fprintln(wr) }