P17380 [PacNW 2025] Bus Seating

A bus has $n$ rows, numbered $1$ through $n$, with $k$ seats in each row. A total of $m$ people will enter the bus. Each person has a favorite row and receives utility $C$ from sitting in that row. If a person's favorite row is $r_x$ and they sit in row $r_y$, their utility before accounting for other passengers is $C-|r_x-r_y|$. However, the passengers are introverts. Each person already sitting in a row halves the utility a new passenger would receive from that row. Formally, if $p$ people are already sitting in row $r_y$, then a passenger whose favorite row is $r_x$ receives $$ \frac{C-|r_x-r_y|}{2^p} $$ utility by sitting in row $r_y$. A row with all $k$ seats occupied cannot be selected. Each person chooses a row that maximizes their utility at the moment they sit down. If several rows give the same maximum utility, they choose the row with the smallest number. Nobody changes rows after sitting down. Determine where every passenger sits.

The first line contains four integers $n$, $k$, $m$, and $C$ ($1\le n,k,m\le2\cdot10^5$, $n\le C\le10^9$, and $m\le n\cdot k$): the number of rows, the number of seats per row, the number of passengers, and the utility of sitting in one's favorite row. The second line contains $m$ integers $a_1,a_2,\ldots,a_m$ ($1\le a_i\le n$), where $a_i$ is passenger $i$'s favorite row. Passengers sit down in input order.

Output one line containing $m$ integers $b_1,b_2,\ldots,b_m$, where $b_i$ is the row chosen by passenger $i$.

In the first sample, the utilities available to each passenger are as follows: 1. A passenger who prefers row $3$ sees utilities $[2,3,4]$ and chooses row $3$. 2. A passenger who prefers row $2$ sees utilities $[3,4,1.5]$ and chooses row $2$. 3. A passenger who prefers row $3$ sees utilities $[2,1.5,2]$ and chooses row $1$. 4. A passenger who prefers row $2$ sees utilities $[1.5,2,1.5]$ and chooses row $2$. 5. A passenger who prefers row $2$ sees utilities $[1.5,1,1.5]$ and chooses row $1$. 6. A passenger who prefers row $1$ sees utilities $[1,0.75,1]$. Row $1$ is full, so they choose row $3$.