Editorial for Sushi Belt Lab

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

We need to support four operations on a sequence:

  • rotate by arbitrary k
  • reverse
  • add d to every element
  • pop from left/right and print

A good way to model this is a collections.deque with two lazy flags:

  • reversed_view: whether logical left/right are swapped.
  • season: global value added to every still-alive plate.

Operations:

  • SHIFT k: call deque.rotate(k) (or rotate(-k) when reversed_view is on).
  • REVERSE: toggle reversed_view, meaning all future endpoint operations are interpreted in the opposite direction.
    • After this, logical L means physical right end, and logical R means physical left end.
    • We do not call deque.reverse(); we only flip interpretation.
  • SEASON d: just do season += d.
  • TAKE L / TAKE R: map logical side through reversed_view, then popleft / pop.

season is only applied when printing a removed value.

Solution (Python)

import sys
from collections import deque


def main() -> None:
    input = sys.stdin.readline

    n, q = map(int, input().split())
    belt = deque(map(int, input().split()))

    reversed_view = False
    season = 0

    out: list[str] = []

    for _ in range(q):
        parts = input().split()
        op = parts[0]

        if op == "SHIFT":
            if not belt:
                continue
            k = int(parts[1])
            if reversed_view:
                k = -k
            belt.rotate(k)
        elif op == "REVERSE":
            reversed_view = not reversed_view
        elif op == "SEASON":
            season += int(parts[1])
        else:  # TAKE
            side = parts[1]
            take_left = side == "L"
            if reversed_view:
                take_left = not take_left
            value = belt.popleft() if take_left else belt.pop()
            out.append(str(value + season))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.