Overview

This problem asks us to find the position after \(K\) transitions from a starting point on a “functional graph” where each cell has exactly one determined next cell.
Since \(K\) can be as large as \(10^{18}\), we cannot simulate one step at a time. Instead, we use doubling (binary lifting) to compute the answer efficiently.

Analysis

First, looking at the rules of the board, we can see that “given the current position \(i\), the next position is uniquely determined.”

• If \(i=N\), it always stays at \(N\)
• If \(i=1\), the parity of \(A_1+A_2\) determines whether we go to \(1\) or \(2\)
• If \(2\le i\le N-1\), the parity of \(A_i+A_{i+1}\) determines whether we go to \(i-1\) or \(i+1\)

In other words, we can precompute nxt[i], the “next cell” for each cell.
Once this is done, the problem reduces to the following:

• There is an array nxt of length \(N\)
• The initial position is 0 (cell 1 in 1-indexed)
• Find the final position after repeating pos = nxt[pos] \(K\) times

---

Why the naive approach doesn’t work

Naively looping \(K\) times takes \(O(K)\).
However, since \(K \le 10^{18}\), this is far too slow.

---

How to solve it

We decompose the \(K\) transitions using binary representation (doubling).

• up[b][i] := “the cell reached after moving \(2^b\) times from cell i”
• up[0][i] = nxt[i]
• up[b+1][i] = up[b][ up[b][i] ]

With this precomputed, we simply look at each bit of \(K\): - If the \(b\)-th bit is 1, then pos = up[b][pos]

This finds the final position in a total of \(O(\log K)\) steps.

Since \(K \le 10^{18} < 2^{60}\), 60 levels are sufficient.

Algorithm

1. Read the input.
2. Special case: if N=1, the answer is always cell 1, so output immediately.
3. Build nxt in 0-indexed form.
   • i=N-1 maps to itself
   • i=0 maps to 0 or 1 based on the parity of (A[0]+A[1])
   • Otherwise, maps to i-1 or i+1 based on the parity of (A[i]+A[i+1])
4. Build the doubling table up (60 levels).
5. Starting from initial position pos=0, jump according to each bit of \(K\).
6. Convert back to 1-indexed and output pos+1.

Complexity

• Time complexity: \(O(N \log K)\)
• Space complexity: \(O(N \log K)\)

Implementation Notes

• Using 0-indexed internally makes implementation easier (just add +1 when outputting).

• Parity checking can be done efficiently with (x & 1). This works fine even for negative numbers in Python.

• LOG=60 is sufficient for \(K\le 10^{18}\).

• Be careful to handle N=1 first; otherwise, accessing A[1] would cause an out-of-bounds error.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    if N == 1:
        print(1)
        return

    # next position for each square (0-indexed)
    nxt = [0] * N
    for i in range(N):
        if i == N - 1:
            nxt[i] = i
        elif i == 0:
            nxt[i] = 1 if ((A[0] + A[1]) & 1) == 0 else 0
        else:
            nxt[i] = i + 1 if ((A[i] + A[i + 1]) & 1) == 0 else i - 1

    LOG = 60  # since K <= 1e18 < 2^60
    up = [nxt]
    for _ in range(1, LOG):
        prev = up[-1]
        cur = [0] * N
        for i in range(N):
            cur[i] = prev[prev[i]]
        up.append(cur)

    pos = 0  # start from square 1 (0-indexed)
    b = 0
    while K:
        if K & 1:
            pos = up[b][pos]
        K >>= 1
        b += 1

    print(pos + 1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.