提出 #6476739


ソースコード 拡げる

Copy
class heaptree():
    L=[None]
    N=0
    def __init__(self):
        self.L=[None]
        self.N=0
    def debug(self):
        return self.L
    def heappush(self,v):
        self.L.append(v)
        self.N+=1
        i=self.N
        while(i>1):
            if self.L[i//2]<self.L[i]:
                self.L[i//2],self.L[i]=self.L[i],self.L[i//2]
                i=i//2
            else:
                break
    def value(self):
        if self.N==0:
            return None
        else:
            return self.L[1]
    def heappop(self):
        if self.value()==None:
            return None
        res=self.L[1]
        self.L[1]=self.L[-1]
        self.L.pop()
        self.N-=1
        i=1
        while(i<=self.N):
            if 2*i+1<=self.N:
                if self.L[i]>self.L[2*i] and self.L[i]>self.L[2*i+1]:
                    break
                elif self.L[2*i]<self.L[2*i+1]:
                    self.L[i],self.L[2*i+1]=self.L[2*i+1],self.L[i]
                    i=2*i+1
                else:
                    self.L[i],self.L[2*i]=self.L[2*i],self.L[i]
                    i=2*i
            elif 2*i==self.N:
                if self.L[i]>self.L[2*i]:
                    break
                else:
                    self.L[i],self.L[2*i]=self.L[2*i],self.L[i]
                    i=2*i
            else:
                break
        return res
N=int(input())
a=[int(input()) for i in range(N)]
Q=heaptree()
Q.heappush(a[0])
for i in range(1,N):
    if a[i]<=Q.value():
        Q.heappush(a[i])
print(Q.N)

提出情報

提出日時
問題 E - Sequence Decomposing
ユーザ shakayami
言語 Python (3.4.3)
得点 0
コード長 1599 Byte
結果 WA
実行時間 317 ms
メモリ 7856 KB

ジャッジ結果

セット名 All Sample
得点 / 配点 0 / 500 0 / 0
結果
AC × 5
WA × 30
AC × 2
セット名 テストケース
All all_same, killer_01, killer_02, killer_03, killer_04, killer_05, many_dup_01, many_dup_02, many_dup_03, many_dup_04, many_dup_05, many_dup_06, many_dup_07, many_dup_08, many_dup_09, many_dup_10, many_dup_11, many_dup_12, rand_max_01, rand_max_02, rand_max_03, rand_max_04, rand_max_05, rand_max_06, rand_max_07, rand_max_08, rand_max_09, rand_max_10, rand_max_11, sample_01, sample_02, sorted_ascending, sorted_descending, unique_perm_01, unique_perm_02
Sample sample_01, sample_02
ケース名 結果 実行時間 メモリ
all_same AC 260 ms 7832 KB
killer_01 WA 258 ms 7732 KB
killer_02 WA 249 ms 7488 KB
killer_03 WA 261 ms 7732 KB
killer_04 WA 234 ms 7472 KB
killer_05 WA 241 ms 7608 KB
many_dup_01 WA 286 ms 7472 KB
many_dup_02 WA 205 ms 6968 KB
many_dup_03 WA 199 ms 6832 KB
many_dup_04 WA 317 ms 7740 KB
many_dup_05 WA 306 ms 7732 KB
many_dup_06 WA 302 ms 7472 KB
many_dup_07 WA 229 ms 7348 KB
many_dup_08 WA 242 ms 7472 KB
many_dup_09 WA 246 ms 7224 KB
many_dup_10 WA 280 ms 7856 KB
many_dup_11 WA 212 ms 7472 KB
many_dup_12 WA 232 ms 7216 KB
rand_max_01 WA 219 ms 7088 KB
rand_max_02 WA 269 ms 7216 KB
rand_max_03 WA 246 ms 6968 KB
rand_max_04 WA 301 ms 7472 KB
rand_max_05 WA 202 ms 6708 KB
rand_max_06 WA 251 ms 7104 KB
rand_max_07 WA 287 ms 7352 KB
rand_max_08 WA 214 ms 6968 KB
rand_max_09 WA 302 ms 7344 KB
rand_max_10 WA 245 ms 7348 KB
rand_max_11 WA 238 ms 7096 KB
sample_01 AC 17 ms 3188 KB
sample_02 AC 17 ms 3188 KB
sorted_ascending AC 186 ms 6964 KB
sorted_descending AC 247 ms 7608 KB
unique_perm_01 WA 303 ms 7484 KB
unique_perm_02 WA 226 ms 7092 KB