結果

問題 No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
ユーザー ID 21712ID 21712
提出日時 2025-01-27 03:16:28
言語 Go
(1.23.4)
結果
AC  
実行時間 3,703 ms / 5,000 ms
コード長 6,285 bytes
コンパイル時間 13,837 ms
コンパイル使用メモリ 244,676 KB
実行使用メモリ 29,444 KB
スコア 18,098,452,450
最終ジャッジ日時 2025-01-27 03:23:33
合計ジャッジ時間 407,416 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 120
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import (
. "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)*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
}
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)/4000
vg := (vr+vl)/8000
tt[rl][vg] = append(tt[rl][vg], i)
}
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 < 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 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 = 5
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))
for it:=0;it<1;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)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0