結果
問題 | No.5010 Better Mo's Algorithm is Needed!! (Unweighted) |
ユーザー |
![]() |
提出日時 | 2025-01-28 10:31:03 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 3,682 ms / 5,000 ms |
コード長 | 1,995 bytes |
コンパイル時間 | 12,257 ms |
コンパイル使用メモリ | 231,160 KB |
実行使用メモリ | 18,428 KB |
スコア | 14,820,445,077 |
最終ジャッジ日時 | 2025-01-28 10:39:02 |
合計ジャッジ時間 | 474,061 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 120 |
ソースコード
package mainimport (. "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)*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}sort.Slice(p, func(i, j int) bool {return ls[p[i]] < ls[p[j]]})var sum int64for i,v:=range p[1:] {sum+=int64(ls[v]-ls[p[i]])}SZ:=int(800*sum/int64(q))offset:=0for k:=0;k<n; k+=SZ {ss:=0for _,i:=range p[offset:] {if ls[i]<k+SZ {ss++} else {break}}pp := p[offset:min(q,offset+ss)]offset+=ssvar less func(i,j int) boolif 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 = 200for 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 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]}}}}for i, vp := range p {if i>0 {Fprint(wr, " ")}Fprint(wr, vp+1)}Fprintln(wr)}