P3090 [USACO13NOV] Empty Stalls G

Farmer John's new barn consists of a huge circle of $N$ stalls ($2 \le N \le 3{,}000{,}000$), numbered $0..N-1$, with stall $N-1$ being adjacent to stall $0$. At the end of each day, FJ's cows arrive back at the barn one by one, each with a preferred stall they would like to occupy. However, if a cow's preferred stall is already occupied by another cow, she scans forward sequentially from this stall until she finds the first unoccupied stall, which she then claims. If she scans past stall $N-1$, she continues scanning from stall $0$. Given the preferred stall of each cow, determine the smallest index of a stall that remains unoccupied after all the cows have returned to the barn. Notice that the answer does not depend on the order in which the cows return. To avoid reading huge amounts of input, the input is specified concisely using $K$ lines ($1 \le K \le 10{,}000$), each of the form: X Y A B One such line specifies preferences for $X \times Y$ cows in total: $X$ cows prefer each of the stalls $f(1), \dots, f(Y)$, where $f(i) = (A i + B) \bmod N$. The values of $A$ and $B$ lie in the range $0 \dots 1{,}000{,}000{,}000$. Note: The standard memory limit is 64 MB.

Farmer John's new barn consists of a huge circle of $N$ stalls ($2 \le N \le 3{,}000{,}000$), numbered $0..N-1$, with stall $N-1$ being adjacent to stall $0$. At the end of each day, FJ's cows arrive back at the barn one by one, each with a preferred stall they would like to occupy. However, if a cow's preferred stall is already occupied by another cow, she scans forward sequentially from this stall until she finds the first unoccupied stall, which she then claims. If she scans past stall $N-1$, she continues scanning from stall $0$. Given the preferred stall of each cow, determine the smallest index of a stall that remains unoccupied after all the cows have returned to the barn. Notice that the answer does not depend on the order in which the cows return. To avoid reading huge amounts of input, the input is specified concisely using $K$ lines ($1 \le K \le 10{,}000$), each of the form: X Y A B One such line specifies preferences for $X \times Y$ cows in total: $X$ cows prefer each of the stalls $f(1), \dots, f(Y)$, where $f(i) = (A i + B) \bmod N$. The values of $A$ and $B$ lie in the range $0 \dots 1{,}000{,}000{,}000$. Note: The standard memory limit is 64 MB.

- Line 1: Two space-separated integers $N$ and $K$. - Lines $2..1+K$: Each line contains integers $X$ $Y$ $A$ $B$, interpreted as above. The total number of cows specified by all lines will be at most $N-1$. Multiple lines may add cows preferring the same stall.

- Line 1: The minimum index of an unoccupied stall.

There are 10 stalls in the barn, numbered $0..9$. The second line of input states that 3 cows prefer stall $(2 \cdot 1 + 4) \bmod 10 = 6$, and 3 cows prefer stall $(2 \cdot 2 + 4) \bmod 10 = 8$. The third line states that 2 cows prefer stall $(0 \cdot 1 + 1) \bmod 10 = 1$. Line four specifies that 1 cow prefers stall $(1 \cdot 1 + 7) \bmod 10 = 8$ (so a total of 4 cows prefer this stall). All stalls will end up occupied except stall 5. Translated by ChatGPT 5