結果

問題 No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
ユーザー ID 21712ID 21712
提出日時 2025-01-28 03:58:19
言語 Go
(1.23.4)
結果
AC  
実行時間 4,510 ms / 5,000 ms
コード長 1,809 bytes
コンパイル時間 13,440 ms
コンパイル使用メモリ 239,972 KB
実行使用メモリ 18,544 KB
スコア 15,307,475,540
最終ジャッジ日時 2025-01-28 04:08:29
合計ジャッジ時間 506,408 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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]]
})
const SZ = 800
for k:=0;k*SZ<n; k++ {
offset := k*SZ
pp := p[offset:min(q,offset+SZ)]
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(SZ+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