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

提出ソース

結果

問題	No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
ユーザー	titia
提出日時	2022-12-17 04:13:49
言語	PyPy3 (7.3.15)
結果	AC
実行時間	4,862 ms / 5,000 ms
コード長	1,812 bytes
コンパイル時間	1,094 ms
実行使用メモリ	188,232 KB
スコア	17,136,370,604
最終ジャッジ日時	2022-12-17 04:24:26
合計ジャッジ時間	630,057 ms
ジャッジサーバーID （参考情報）	judge16 / judge10
	純コード判定しない問題か言語

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	4,856 ms 181,932 KB
testcase_01	AC	4,841 ms 183,928 KB
testcase_02	AC	4,852 ms 185,416 KB
testcase_03	AC	4,853 ms 179,924 KB
testcase_04	AC	4,844 ms 185,096 KB
testcase_05	AC	4,846 ms 178,720 KB
testcase_06	AC	4,839 ms 184,324 KB
testcase_07	AC	4,845 ms 180,164 KB
testcase_08	AC	4,848 ms 182,020 KB
testcase_09	AC	4,847 ms 181,212 KB
testcase_10	AC	4,842 ms 184,196 KB
testcase_11	AC	4,846 ms 182,720 KB
testcase_12	AC	4,845 ms 178,984 KB
testcase_13	AC	4,844 ms 181,960 KB
testcase_14	AC	4,845 ms 182,884 KB
testcase_15	AC	4,847 ms 179,828 KB
testcase_16	AC	4,854 ms 186,528 KB
testcase_17	AC	4,849 ms 179,588 KB
testcase_18	AC	4,838 ms 183,148 KB
testcase_19	AC	4,842 ms 188,232 KB
testcase_20	AC	4,845 ms 183,260 KB
testcase_21	AC	4,842 ms 183,076 KB
testcase_22	AC	4,851 ms 185,244 KB
testcase_23	AC	4,849 ms 181,920 KB
testcase_24	AC	4,841 ms 183,348 KB
testcase_25	AC	4,842 ms 185,444 KB
testcase_26	AC	4,847 ms 183,472 KB
testcase_27	AC	4,840 ms 181,292 KB
testcase_28	AC	4,840 ms 182,240 KB
testcase_29	AC	4,847 ms 181,212 KB
testcase_30	AC	4,844 ms 179,896 KB
testcase_31	AC	4,843 ms 180,664 KB
testcase_32	AC	4,844 ms 180,056 KB
testcase_33	AC	4,845 ms 183,676 KB
testcase_34	AC	4,844 ms 183,980 KB
testcase_35	AC	4,842 ms 184,528 KB
testcase_36	AC	4,843 ms 182,656 KB
testcase_37	AC	4,846 ms 183,308 KB
testcase_38	AC	4,845 ms 185,648 KB
testcase_39	AC	4,844 ms 178,776 KB
testcase_40	AC	4,850 ms 184,312 KB
testcase_41	AC	4,840 ms 179,900 KB
testcase_42	AC	4,842 ms 177,916 KB
testcase_43	AC	4,840 ms 182,836 KB
testcase_44	AC	4,845 ms 182,012 KB
testcase_45	AC	4,843 ms 180,688 KB
testcase_46	AC	4,841 ms 184,644 KB
testcase_47	AC	4,844 ms 179,412 KB
testcase_48	AC	4,843 ms 179,712 KB
testcase_49	AC	4,841 ms 186,364 KB
testcase_50	AC	4,846 ms 178,656 KB
testcase_51	AC	4,843 ms 179,868 KB
testcase_52	AC	4,841 ms 182,204 KB
testcase_53	AC	4,862 ms 174,980 KB
testcase_54	AC	4,846 ms 176,184 KB
testcase_55	AC	4,843 ms 183,260 KB
testcase_56	AC	4,841 ms 184,816 KB
testcase_57	AC	4,840 ms 182,436 KB
testcase_58	AC	4,845 ms 185,100 KB
testcase_59	AC	4,845 ms 179,112 KB
testcase_60	AC	4,844 ms 180,536 KB
testcase_61	AC	4,840 ms 184,992 KB
testcase_62	AC	4,838 ms 179,764 KB
testcase_63	AC	4,839 ms 175,164 KB
testcase_64	AC	4,838 ms 181,012 KB
testcase_65	AC	4,840 ms 184,960 KB
testcase_66	AC	4,840 ms 181,924 KB
testcase_67	AC	4,836 ms 184,316 KB
testcase_68	AC	4,846 ms 183,788 KB
testcase_69	AC	4,840 ms 180,324 KB
testcase_70	AC	4,841 ms 184,036 KB
testcase_71	AC	4,843 ms 186,472 KB
testcase_72	AC	4,840 ms 179,644 KB
testcase_73	AC	4,845 ms 186,476 KB
testcase_74	AC	4,841 ms 181,812 KB
testcase_75	AC	4,840 ms 180,920 KB
testcase_76	AC	4,843 ms 187,432 KB
testcase_77	AC	4,847 ms 179,876 KB
testcase_78	AC	4,843 ms 181,100 KB
testcase_79	AC	4,845 ms 184,648 KB
testcase_80	AC	4,846 ms 186,364 KB
testcase_81	AC	4,855 ms 181,288 KB
testcase_82	AC	4,843 ms 182,672 KB
testcase_83	AC	4,842 ms 183,344 KB
testcase_84	AC	4,844 ms 179,624 KB
testcase_85	AC	4,842 ms 185,440 KB
testcase_86	AC	4,840 ms 180,868 KB
testcase_87	AC	4,845 ms 180,108 KB
testcase_88	AC	4,853 ms 185,340 KB
testcase_89	AC	4,856 ms 181,932 KB
testcase_90	AC	4,843 ms 178,720 KB
testcase_91	AC	4,841 ms 184,932 KB
testcase_92	AC	4,841 ms 182,000 KB
testcase_93	AC	4,844 ms 177,232 KB
testcase_94	AC	4,845 ms 183,624 KB
testcase_95	AC	4,860 ms 181,364 KB
testcase_96	AC	4,850 ms 174,380 KB
testcase_97	AC	4,842 ms 185,276 KB
testcase_98	AC	4,848 ms 182,352 KB
testcase_99	AC	4,842 ms 179,968 KB
testcase_100	AC	4,846 ms 183,876 KB
testcase_101	AC	4,844 ms 179,248 KB
testcase_102	AC	4,843 ms 179,356 KB
testcase_103	AC	4,842 ms 182,704 KB
testcase_104	AC	4,846 ms 186,076 KB
testcase_105	AC	4,846 ms 179,160 KB
testcase_106	AC	4,844 ms 184,460 KB
testcase_107	AC	4,845 ms 180,024 KB
testcase_108	AC	4,852 ms 178,044 KB
testcase_109	AC	4,849 ms 182,948 KB
testcase_110	AC	4,844 ms 179,404 KB
testcase_111	AC	4,841 ms 178,544 KB
testcase_112	AC	4,847 ms 184,280 KB
testcase_113	AC	4,843 ms 180,332 KB
testcase_114	AC	4,848 ms 180,252 KB
testcase_115	AC	4,848 ms 185,160 KB
testcase_116	AC	4,843 ms 179,768 KB
testcase_117	AC	4,847 ms 179,068 KB
testcase_118	AC	4,843 ms 185,132 KB
testcase_119	AC	4,846 ms 177,944 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//530].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

結果

テストケース

ソースコード