P3972 [TJOI2014] Movie Rating

Xiao Z invented a new movie rating system with three kinds of operations: releasing a new movie, rating a movie, and querying a movie’s rank. - When releasing a new movie: if none of its leading actors have appeared before, the new movie’s rating is $0$. Otherwise, its initial rating equals the rating of the most recent previously released movie that shares at least one leading actor with it. - When rating a movie: its rating becomes the average of its previous rating and the new score. - When querying a rank: output the ID of the movie whose current rank is $x$. The highest rating ranks first. If multiple movies have the same rating, the one released earlier ranks higher. All ratings are between $0$ and $5$.

The first line contains $n$, the number of operations. Then $n$ lines follow, each being one of the following: 1. Q x: query the movie ID currently ranked $x$. 2. R ID x actor1 actor2 ... actorx: release a new movie with ID $ID$, which has $x$ leading actors $actor1, actor2, \dots, actorx$. 3. C ID score: rate movie $ID$ with the score $score$; the movie’s new rating becomes the average of its previous rating and $score$. Additional rules: - All movie IDs are distinct. - Each movie has at most $5$ leading actors. Constraints: - $1 \leq actor_i \leq 10^5$. - $1 \leq ID \leq 10^5$. - For $30\%$ of the testdata, $n \leq 100$. - For $100\%$ of the testdata, $n \leq 10000$.

For each query operation, output the corresponding movie ID.

- The initial rating of a new movie is $0$ if none of its leading actors have appeared before; otherwise, it equals the rating of the most recently released earlier movie that shares at least one leading actor. - After a rating operation C ID score, the new rating becomes the average of the current rating and $score$. - If multiple movies have the same rating, the earlier released one ranks higher. For example, if Movie $2$ and Movie $3$ have the same rating, then a query Q $1$ returns $2$ because Movie $2$ was released earlier. Translated by ChatGPT 5