#826350 (PyPy3) No.5010 Better Mo's Algorithm is Needed!! (Unweighted)

提出ソース

結果

問題	No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
ユーザー	titia
提出日時	2022-12-17 03:27:37
言語	PyPy3 (7.3.15)
結果	AC
実行時間	4,928 ms / 5,000 ms
コード長	1,830 bytes
コンパイル時間	974 ms
実行使用メモリ	187,872 KB
スコア	16,985,670,009
最終ジャッジ日時	2022-12-17 03:38:14
合計ジャッジ時間	632,507 ms
ジャッジサーバーID （参考情報）	judge16 / judge11
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4,879 ms 179,152 KB
testcase_01	AC	4,853 ms 181,060 KB
testcase_02	AC	4,851 ms 180,192 KB
testcase_03	AC	4,854 ms 177,372 KB
testcase_04	AC	4,848 ms 185,480 KB
testcase_05	AC	4,852 ms 179,384 KB
testcase_06	AC	4,855 ms 180,240 KB
testcase_07	AC	4,851 ms 182,636 KB
testcase_08	AC	4,852 ms 178,732 KB
testcase_09	AC	4,852 ms 182,336 KB
testcase_10	AC	4,855 ms 183,396 KB
testcase_11	AC	4,850 ms 181,156 KB
testcase_12	AC	4,847 ms 179,644 KB
testcase_13	AC	4,850 ms 182,188 KB
testcase_14	AC	4,852 ms 181,920 KB
testcase_15	AC	4,846 ms 179,040 KB
testcase_16	AC	4,848 ms 182,008 KB
testcase_17	AC	4,849 ms 178,224 KB
testcase_18	AC	4,852 ms 177,868 KB
testcase_19	AC	4,850 ms 186,320 KB
testcase_20	AC	4,853 ms 180,348 KB
testcase_21	AC	4,853 ms 178,276 KB
testcase_22	AC	4,854 ms 181,604 KB
testcase_23	AC	4,847 ms 182,228 KB
testcase_24	AC	4,850 ms 180,932 KB
testcase_25	AC	4,867 ms 181,396 KB
testcase_26	AC	4,846 ms 182,492 KB
testcase_27	AC	4,849 ms 180,756 KB
testcase_28	AC	4,847 ms 185,228 KB
testcase_29	AC	4,854 ms 181,788 KB
testcase_30	AC	4,852 ms 180,348 KB
testcase_31	AC	4,848 ms 183,684 KB
testcase_32	AC	4,850 ms 182,136 KB
testcase_33	AC	4,849 ms 179,512 KB
testcase_34	AC	4,852 ms 185,684 KB
testcase_35	AC	4,849 ms 180,936 KB
testcase_36	AC	4,846 ms 178,520 KB
testcase_37	AC	4,855 ms 182,460 KB
testcase_38	AC	4,861 ms 186,368 KB
testcase_39	AC	4,844 ms 178,868 KB
testcase_40	AC	4,841 ms 182,092 KB
testcase_41	AC	4,861 ms 181,412 KB
testcase_42	AC	4,842 ms 175,692 KB
testcase_43	AC	4,846 ms 184,928 KB
testcase_44	AC	4,843 ms 177,360 KB
testcase_45	AC	4,844 ms 179,860 KB
testcase_46	AC	4,842 ms 187,556 KB
testcase_47	AC	4,850 ms 181,596 KB
testcase_48	AC	4,854 ms 177,592 KB
testcase_49	AC	4,841 ms 183,964 KB
testcase_50	AC	4,841 ms 180,232 KB
testcase_51	AC	4,844 ms 176,300 KB
testcase_52	AC	4,843 ms 178,508 KB
testcase_53	AC	4,841 ms 185,084 KB
testcase_54	AC	4,845 ms 181,132 KB
testcase_55	AC	4,838 ms 180,452 KB
testcase_56	AC	4,839 ms 183,712 KB
testcase_57	AC	4,843 ms 176,664 KB
testcase_58	AC	4,838 ms 183,760 KB
testcase_59	AC	4,838 ms 185,104 KB
testcase_60	AC	4,845 ms 177,828 KB
testcase_61	AC	4,839 ms 180,780 KB
testcase_62	AC	4,837 ms 178,572 KB
testcase_63	AC	4,848 ms 182,720 KB
testcase_64	AC	4,844 ms 184,044 KB
testcase_65	AC	4,841 ms 180,876 KB
testcase_66	AC	4,839 ms 180,980 KB
testcase_67	AC	4,841 ms 183,908 KB
testcase_68	AC	4,841 ms 177,236 KB
testcase_69	AC	4,839 ms 175,932 KB
testcase_70	AC	4,844 ms 183,712 KB
testcase_71	AC	4,842 ms 177,612 KB
testcase_72	AC	4,846 ms 181,032 KB
testcase_73	AC	4,848 ms 184,376 KB
testcase_74	AC	4,837 ms 179,280 KB
testcase_75	AC	4,843 ms 182,476 KB
testcase_76	AC	4,836 ms 181,792 KB
testcase_77	AC	4,840 ms 179,484 KB
testcase_78	AC	4,844 ms 180,836 KB
testcase_79	AC	4,864 ms 185,548 KB
testcase_80	AC	4,928 ms 184,336 KB
testcase_81	AC	4,846 ms 179,872 KB
testcase_82	AC	4,836 ms 181,988 KB
testcase_83	AC	4,842 ms 180,688 KB
testcase_84	AC	4,839 ms 182,176 KB
testcase_85	AC	4,856 ms 181,724 KB
testcase_86	AC	4,845 ms 182,220 KB
testcase_87	AC	4,845 ms 180,672 KB
testcase_88	AC	4,842 ms 184,608 KB
testcase_89	AC	4,843 ms 180,792 KB
testcase_90	AC	4,848 ms 171,400 KB
testcase_91	AC	4,838 ms 186,400 KB
testcase_92	AC	4,847 ms 182,536 KB
testcase_93	AC	4,851 ms 180,540 KB
testcase_94	AC	4,845 ms 184,584 KB
testcase_95	AC	4,839 ms 180,384 KB
testcase_96	AC	4,841 ms 181,280 KB
testcase_97	AC	4,840 ms 186,324 KB
testcase_98	AC	4,839 ms 180,964 KB
testcase_99	AC	4,842 ms 182,456 KB
testcase_100	AC	4,864 ms 182,888 KB
testcase_101	AC	4,850 ms 182,404 KB
testcase_102	AC	4,842 ms 179,048 KB
testcase_103	AC	4,836 ms 181,512 KB
testcase_104	AC	4,837 ms 181,800 KB
testcase_105	AC	4,842 ms 180,084 KB
testcase_106	AC	4,842 ms 185,064 KB
testcase_107	AC	4,858 ms 179,352 KB
testcase_108	AC	4,849 ms 178,944 KB
testcase_109	AC	4,836 ms 184,944 KB
testcase_110	AC	4,838 ms 183,584 KB
testcase_111	AC	4,843 ms 180,584 KB
testcase_112	AC	4,838 ms 185,244 KB
testcase_113	AC	4,840 ms 183,960 KB
testcase_114	AC	4,838 ms 180,880 KB
testcase_115	AC	4,841 ms 186,484 KB
testcase_116	AC	4,842 ms 180,560 KB
testcase_117	AC	4,842 ms 181,496 KB
testcase_118	AC	4,841 ms 187,872 KB
testcase_119	AC	4,846 ms 179,776 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
input = sys.stdin.readline
from operator import itemgetter
import time
from random import randint

time0=time.time()

N,Q,WT,ST=map(int,input().split())
W=list(map(int,input().split()))
LR=[list(map(int,input().split()))+[i+1] for i in range(Q)]

LR2=sorted(LR,key=itemgetter(0))

LIST=[[] for i in range(1000)]

for x,y,ind in LR2:
    LIST[x//500].append((y,ind))

ANS=[]

count=0
for i in range(1000):
    if LIST[i]==[]:
        continue
    if count%2==0:
        LIST[i].sort(key=itemgetter(0))
    else:
        LIST[i].sort(key=itemgetter(0),reverse=True)
        
    for _,ind in LIST[i]:
        ANS.append(ind)

    count+=1

SUM=[0]

for w in W:
    SUM.append(SUM[-1]+w)

def score(x,y):
    if x==-1:
        a,b,_=LR[y-1]
        return SUM[b]-SUM[a-1]
    else:
        a,b,_=LR[y-1]
        c,d,_=LR[x-1]

        a2,b2=min(a,c),max(a,c)
        c2,d2=min(b,d),max(b,d)

        return SUM[b2-1]-SUM[a2-1]+SUM[d2]-SUM[c2]
    
def score_reverse(x,y):
    sc=0

    if x==0:
        a=ANS[x]
        b=ANS[y]
        c=ANS[y+1]

        sc-=score(-1,a)+score(a,b)+score(b,c)
        sc+=score(-1,b)+score(b,a)+score(a,c)

        return sc

    if y==len(ANS)-1:
        a=ANS[x-1]
        b=ANS[x]
        c=ANS[y]

        sc-=score(a,b)+score(b,c)
        sc+=score(a,c)+score(c,b)

        return sc

    a=ANS[x-1]
    b=ANS[x]
    c=ANS[y]
    d=ANS[y+1]

    sc-=score(a,b)+score(b,c)+score(c,d)
    sc+=score(a,c)+score(c,b)+score(b,d)

    return sc

def last_score(ANS):
    sc=0
    for i in range(len(ANS)):
        if i==0:
            sc+=score(-1,ANS[0])
        else:
            sc+=score(ANS[i-1],ANS[i])

    return sc
    
while time.time()-time0<4.7:
    k=randint(0,len(ANS)-2)

    if score_reverse(k,k+1)<0:
        ANS[k],ANS[k+1]=ANS[k+1],ANS[k]

print(*ANS)

yukicoder

結果

テストケース

ソースコード