Problem: Link

Submission: Link $$$O(n)$$$, 92ms!

Part1: Hint

By looking at the $$$4$$$ test cases, we find that answers for $$$b[i] = 1$$$ are the same.

Part2: The greedy strategy (for each index $$$i$$$)

First, we define some macros for convenience:

The previous index of $$$x$$$: #define pr(x) ((x) == 1 ? n : (x) - 1)

The next index of $$$x$$$: #define ne(x) ((x) == n ? 1 : (x) + 1)

If $$$b[x]==1$$$, rt(x) denotes the place of the next $$$1$$$ in the loop: rt(x). For example, let $$$b$$$ be an $$$1$$$-indexed array $$$[2, 1, 2, 1]$$$, then $$$rt(2)==4$$$ and $$$rt(4)==2$$$. Note that $$$rt(i)==i$$$ could happen, for example, $$$b==[2, 1, 2]$$$, then $$$rt(2)==2$$$. rt could be pre-calculated using a stack.

get(i, j): The gas need to go from $$$i$$$ to $$$j$$$, both inclusive and $$$1$$$-indexed. For example, if $$$a=[1, 2, 3, 4]$$$, then $$$get(1, 2)==1+2==3$$$ and $$$get(4, 2)==4+1+2==7$$$. The $$$get$$$ function could be pre-calculated using the prefix sum.

//The Initialpoint
int i = initialpoint;
while(true){
    (1) If you are at the destination, which is the same as the initialpoint, break out of this while loop.

    (2) When you stay at i where b[i]==2, just pay 2a[i] for a[i] gas that enables you to move from i to ne(i). let i = ne(i);

    (3) When you stay at i where b[i]==1, set initialized2 = true and curi = i, and do the following inner while loop:
    while(initialized2 || curi != rt(i)){ //rt(i): The next i in this trip with b[i]==1
        
        curi = ne(curi);
    }
}
outer loop: