結果
問題 |
No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
|
ユーザー |
![]() |
提出日時 | 2025-01-28 14:23:33 |
言語 | Go (1.23.4) |
結果 |
RE
|
実行時間 | - |
コード長 | 6,601 bytes |
コンパイル時間 | 12,266 ms |
コンパイル使用メモリ | 240,608 KB |
実行使用メモリ | 27,204 KB |
スコア | 144,339,424 |
最終ジャッジ日時 | 2025-01-28 14:24:34 |
合計ジャッジ時間 | 57,488 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 RE * 119 |
ソースコード
package main import ( . "fmt" . "os" bf "bufio" "container/list" "math" "math/rand" "sort" ) 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)*100 t += int64(v-u)*100 return } func main() { rd:=bf.NewReader(Stdin) wr:=bf.NewWriter(Stdout) defer wr.Flush() var n,q,wt,st int Fscan(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 } const SZ = 50 tt := make([][][]int, SZ) tte := make([][][]*list.Element, SZ) for i := range tt { tt[i] = make([][]int, SZ) tte[i] = make([][]*list.Element, SZ) } for i,vl := range ls { vr := rs[i] rl := vl/((n+SZ-1)/SZ) vg := vr/((n+SZ-1)/SZ) tt[rl][vg] = append(tt[rl][vg], i) } const SORT = false if SORT { for _, tt0 := range tt { for _, tt1 := range tt0 { sort.Slice(tt1, func(i,j int) bool { return rs[i]-ls[i]>rs[j]-ls[j] }) } } } used := make([]bool, q) plist := list.New() { var best int64 = math.MaxInt64 var bestvg int = -1 var bestti int = -1 var bestrl int = -1 for rl, tt0 := range tt { 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 bestrl = rl } } } } if best < math.MaxInt64 { tt1 := tt[bestrl][bestvg] tt1[0],tt1[bestti] = tt1[bestti],tt1[0] i := tt1[0] tt[bestrl][bestvg] = tt1[1:] elem := plist.PushBack(i) tte[bestrl][bestvg] = append(tte[bestrl][bestvg], elem) used[i] = true } } for _, rl := range rand.Perm(SZ) { for _, vg := range rand.Perm(SZ) { 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() } } const TWOOPT = 0 for j := 0; j < TWOOPT ; j++ { for i := range rand.Perm(q) { k := min(rand.Intn(500+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<g ; f,g =f+1,g-1 { p[f],p[g]=p[g],p[f] } } } } perm4 := [][]int{} const PS = 4 var 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] = i makeperm(n+1,v|(1<<i),ps) } } makeperm(0,0,make([]int,PS)) const PERM4 = 0 for it:=0; it < PERM4 ;it++ { for i := range rand.Perm(q) { if i+PS-1 >= 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<PS; j++ { if i+j+1 < len(p) { t1 += parttime(ls,rs,p, i+j,i+j+1) } } if t1 < t0 { t0 = t1 bestpmi = 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) }