結果

問題 No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
ユーザー ID 21712ID 21712
提出日時 2025-01-28 11:12:50
言語 Go
(1.23.4)
結果
AC  
実行時間 3,965 ms / 5,000 ms
コード長 1,995 bytes
コンパイル時間 14,171 ms
コンパイル使用メモリ 255,388 KB
実行使用メモリ 18,448 KB
スコア 14,559,400,907
最終ジャッジ日時 2025-01-28 11:22:02
合計ジャッジ時間 497,321 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 120
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
. "fmt"
. "os"
bf "bufio"
"sort"
"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 abs(a int64) int64 {
if a < 0 {
return -a
}
return a
}
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
}
sort.Slice(p, func(i, j int) bool {
return ls[p[i]] < ls[p[j]]
})
var sum int64
for i,v:=range p[1:] {
sum+=int64(ls[v]-ls[p[i]])
}
SZ:=int(800*sum/int64(q))
offset:=0
for k:=0;k<n; k+=SZ {
ss:=0
for _,i:=range p[offset:] {
if ls[i]<k+SZ {
ss++
} else {
break
}
}
pp := p[offset:min(q,offset+ss)]
offset+=ss
var less func(i,j int) bool
if k%2==0 {
less = func(i,j int) bool {
return rs[pp[i]]<rs[pp[j]]
}
} else {
less = func(i,j int) bool {
return rs[pp[i]]>rs[pp[j]]
}
}
sort.Slice(pp, less)
}
const TWOOPT = 200
for j := 0; j < TWOOPT ; j++ {
for i := range rand.Perm(q) {
k := min(rand.Intn(800+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]
}
}
}
}
for i, vp := range p {
if i>0 {
Fprint(wr, " ")
}
Fprint(wr, vp+1)
}
Fprintln(wr)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0