Submission #67130288

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
T=int(input())
for _ in range(T):
    N=int(input())
    S=[0]+list(map(int, input().split()))
    INF=10**18
    dist=[INF]*(N+1)
    dist[1]=1
    rem=sorted((S[i],i) for i in range(2,N+1))
    p=0
    q=deque([1])
    while q:
        i=q.popleft()
        lim=2*S[i]
        while p<len(rem) and rem[p][0]<=lim:
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque
T=int(input())
for _ in range(T):
    N=int(input())
    S=[0]+list(map(int, input().split()))


    INF=10**18
    dist=[INF]*(N+1)
    dist[1]=1


    rem=sorted((S[i],i) for i in range(2,N+1))
    p=0

    q=deque([1])
    while q:
        i=q.popleft()
        lim=2*S[i]

        while p<len(rem) and rem[p][0]<=lim:
            sj, j=rem[p]
            dist[j]=dist[i]+1
            q.append(j)
            p+=1
            if j==N:
                q.clear()
                break
        if dist[N]!=INF:
            break

    if dist[N]==INF:
        print(-1)
    else:
        print(dist[N])

Submission Info

Judge Result