1503. Where Position k Lands

An R by C grid is numbered 1 to R * C in clockwise spiral order from the top-left cell, exactly as problem 1502 fills one. The grid itself is never given. Only R, C and q positions arrive.

For each position k, print the 1-based row and column of the cell that holds it.

R = 3, C = 4 k = 1 -> 1 1 k = 4 -> 1 4 k = 7 -> 3 3 k = 12 -> 2 3

R = 1, C = 9 k = 5 -> 1 5 every position stays on row 1

## What most people try first

Walk the spiral. It is obviously correct and it is O(R C) per query, or O(R C) once if the whole order is stored. Here R and C reach 10^9, so R * C reaches 10^18 cells. Storing the order is impossible and walking it once is 10^18 steps.

## Cells before ring t, in closed form

Rings 0 through t - 1 are everything OUTSIDE the sub-rectangle that ring t bounds, and that sub-rectangle is (R - 2t) by (C - 2t). So

before(t) = R * C - max(0, R - 2t) * max(0, C - 2t)

with no case analysis at all: a degenerate ring falls out of the same formula because the rectangle inside it is empty. before is strictly increasing while a ring exists, so a binary search finds the ring holding k in at most 30 steps.

## Walking one ring by arithmetic

With t known, let off = k - before(t) - 1 and h = R - 2t, w = C - 2t.

if h == 1: row t, column t + off if w == 1: row t + off, column t off < w: row t, column t + off the top side off < w + h - 1: row t + 1 + (off - w), column t + w - 1 the right side off < 2w + h - 2: row t + h - 1, column t + w - 2 - (off - w - h + 1) otherwise: row t + h - 2 - (off - 2w - h + 2), column t

## Why the two degenerate cases come first

A ring with h == 1 is a single row and has w cells, not 2(h + w) - 4. Feeding h = 1 into the four-side formula gives 2w - 2 cells, so every position past the first w is wrong. The same applies to w == 1. A square grid never produces either, which is why this is the bug that survives testing.

## Overflow

R * C reaches 10^18 and k reaches 10^18, both far past the 2147483647 a signed 32 bit integer holds, so every product and every comparison here needs 64 bits. The ring index, the row and the column all stay under 10^9 and would each fit in 32; it is the products that do not.

## Cost

O(log min(R, C)) per query, about 30 steps, and O(1) memory. No grid is ever built.

Constraints - `1 ≤ R ≤ 10^9` - `1 ≤ C ≤ 10^9` - `R * C ≤ 10^18` - `1 ≤ q ≤ 200000` - `1 ≤ k ≤ R * C` - `R` and `C` are independent; the grid need not be square