Submission #856697


Source Code Expand

Copy
n = int(raw_input())
har = map(int , raw_input().split())
L = int(raw_input())
q = int(raw_input())

from collections import deque

def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])
 
 
def s_p(g, start, end):
    parents = {}
    for parent, child in bfs(g, start):
        parents[child] = parent
        if child == end:
            revpath = [end]
            while True:
                parent = parents[child]
                revpath.append(parent)
                if parent == start:
                    break
                child = parent
            return list(reversed(revpath))
    return None # or raise appropriate exception

graph = {i:[] for i in xrange(n)}
for i in xrange(n):
    if i - 1 >= 0:graph[i].append(i-1)
    if i + 1 <= n-1:graph[i].append(i+1)
for i in xrange(q):
    a,b = map(int , raw_input().split())
    a-=1
    b-=1
    path = s_p(graph,a,b)
    ans = 0
    sm = 0
    #print path
    pre = har[path[0]]
    psm = 0
    cost = []
    pp = 0
    for ix in xrange(1,len(path)):
        sm += abs(har[path[ix]] - pre)
        psm += abs(har[path[ix]] - pre)
        pre = har[path[ix]]
        if sm > L:
          ans += 1
          sm -= pp
        if sm == L:
          sm = 0
          ans += 1
        cost.append(sm)
        pp = sm
    if sm > 0:
        ans += 1
    print ans
        

Submission Info

Submission Time
Task C - Tak and Cards
User har_vi
Language PyPy2 (5.6.0)
Score 0
Code Size 1609 Byte
Status RE
Exec Time 73 ms
Memory 9072 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 0 / 200 0 / 100
Status
RE × 4
RE × 12
RE × 24
Set Name Test Cases
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
Case Name Status Exec Time Memory
example_01.txt RE 73 ms 9072 KB
example_02.txt RE 59 ms 8944 KB
example_03.txt RE 59 ms 8944 KB
example_04.txt RE 58 ms 8944 KB
subtask1_01.txt RE 59 ms 8944 KB
subtask1_02.txt RE 62 ms 8944 KB
subtask1_03.txt RE 63 ms 8944 KB
subtask1_04.txt RE 63 ms 8944 KB
subtask1_05.txt RE 63 ms 8944 KB
subtask1_06.txt RE 62 ms 8944 KB
subtask1_07.txt RE 60 ms 8944 KB
subtask1_08.txt RE 63 ms 8944 KB
subtask1_09.txt RE 63 ms 8944 KB
subtask2_01.txt RE 63 ms 8944 KB
subtask2_02.txt RE 63 ms 8944 KB
subtask2_03.txt RE 63 ms 8944 KB
subtask2_04.txt RE 63 ms 8944 KB
subtask2_05.txt RE 65 ms 8944 KB
subtask2_06.txt RE 61 ms 8944 KB
subtask2_07.txt RE 60 ms 8944 KB
subtask2_08.txt RE 63 ms 8944 KB
subtask2_09.txt RE 64 ms 8944 KB
subtask2_10.txt RE 65 ms 8944 KB
subtask2_11.txt RE 64 ms 8944 KB