結果
問題 | No.5010 Better Mo's Algorithm is Needed!! (Unweighted) |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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]]})const SZ = 800for k:=0;k*SZ<n; k++ {offset := k*SZpp := p[offset:min(q,offset+SZ)]var 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(SZ+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)}