結果
問題 | No.5010 Better Mo's Algorithm is Needed!! (Unweighted) |
ユーザー |
![]() |
提出日時 | 2025-01-27 03:24:36 |
言語 | Go (1.23.4) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,285 bytes |
コンパイル時間 | 12,743 ms |
コンパイル使用メモリ | 233,884 KB |
実行使用メモリ | 43,224 KB |
スコア | 0 |
最終ジャッジ日時 | 2025-01-27 03:37:19 |
合計ジャッジ時間 | 757,202 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | TLE * 120 |
ソースコード
package mainimport (. "fmt". "os"bf "bufio""container/list""math""math/rand")func min(a,b int) int {if a<b {return a}return b}func max(a,b int) int {return a+b-min(a,b)}func parttime(ls,rs,p []int, i,j int) (t int64) {pi := p[i]a, b := ls[pi], rs[pi]pj := p[j]c, d := ls[pj], rs[pj]x,y:=min(a,c),max(a,c)u,v:=min(b,d),max(b,d)t += int64(y-x)*100t += int64(v-u)*100return}func main() {rd:=bf.NewReader(Stdin)wr:=bf.NewWriter(Stdout)defer wr.Flush()var n,q,wt,st intFscan(rd,&n,&q,&wt,&st)ws := make([]int, n)ls := make([]int, q)rs := make([]int, q)p := make([]int, q)for i := range ws {Fscan(rd,&ws[i])}for i := range ls {Fscan(rd,&ls[i],&rs[i])p[i] = i}tt := make([][][]int, 50)tte := make([][][]*list.Element, 50)for i := range tt {tt[i] = make([][]int, 50)tte[i] = make([][]*list.Element, 50)}for i,vl := range ls {vr := rs[i]rl := (vr-vl)/4000vg := (vr+vl)/8000tt[rl][vg] = append(tt[rl][vg], i)}used := make([]bool, q)plist := list.New()loop1:for rl,tt0 := range tt {var best int64 = math.MaxInt64var bestvg int = -1var bestti int = -1for vg,tt1:= range tt0 {for i, t := range tt1 {value := int64(rs[t]-ls[t]+1)*100if value < best {best = valuebestvg = vgbestti = 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] = truebreak 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 int64var bestElem *list.Element{i := elem.Value.(int)best = -int64(rs[i]-ls[i]+1)*100best += int64(rs[t]-ls[t]+1)*100best += 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 = diffbestElem = elem}} else {diff := parttime(ls,rs,p, i,t)if diff < best {best = diffbestElem = 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.MaxInt64var bestElem *list.Elementfor _, 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 = diffbestElem = prev}} else {diff :=-int64(rs[i]-ls[i]+1)*100diff += int64(rs[t]-ls[t]+1)*100diff += parttime(ls,rs,p, t, i)if diff < best {best = diffbestElem = 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 = diffbestElem = elem}} else {diff := parttime(ls,rs,p, i, t)if diff < best {best = diffbestElem = 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 < 0; 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 int64if 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)*100t1 += 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<g ; f,g =f+1,g-1 {p[f],p[g]=p[g],p[f]}}}}perm4 := [][]int{}const PS = 6var makeperm func(n,v int, ps []int)makeperm = func(n,v int, ps[]int) {if n == PS {tmp := make([]int, PS)copy(tmp, ps)perm4 = append(perm4, tmp)return}for i:=0;i<PS; i++ {if (v&(1<<i)) != 0 {continue}ps[n] = imakeperm(n+1,v|(1<<i),ps)}}makeperm(0,0,make([]int,PS))for it:=0;it<1;it++ {for i := range rand.Perm(q) {if i+PS-1 >= len(p) {continue}var t0 int64if 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]intcopy(orig[:], p[i:i+PS])var bestpmi int = -1for pmi, pm := range perm4 {var t1 int64for 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<PS; j++ {if i+j+1 < len(p) {t1 += parttime(ls,rs,p, i+j,i+j+1)}}if t1 < t0 {t0 = t1bestpmi = pmi}}if bestpmi >= 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)}