結果
問題 | No.5010 Better Mo's Algorithm is Needed!! (Unweighted) |
ユーザー |
![]() |
提出日時 | 2025-01-28 09:57:04 |
言語 | Go (1.23.4) |
結果 |
AC
|
実行時間 | 376 ms / 5,000 ms |
コード長 | 1,445 bytes |
コンパイル時間 | 13,680 ms |
コンパイル使用メモリ | 237,072 KB |
実行使用メモリ | 12,048 KB |
スコア | 13,638,265,588 |
最終ジャッジ日時 | 2025-01-28 09:58:44 |
合計ジャッジ時間 | 92,944 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 120 |
ソースコード
package mainimport (. "fmt". "os"bf "bufio""sort")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(448*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)}for i, vp := range p {if i>0 {Fprint(wr, " ")}Fprint(wr, vp+1)}Fprintln(wr)}