[USACO23OPEN] Rotate and Shift B

Luogu

IDLGP9185

Time4000ms

Memory256MB

DifficultyP4

模拟数学倍增USACO2023

**Note: The time limit for this problem is 4s, 2x the default.** To celebrate the start of spring, Farmer John's $N$ cows have invented an intriguing new dance, where they stand in a circle and re-order themselves in a predictable way. Specifically, there are $N$ positions around the circle, numbered sequentially from $0$ to $N-1$, with position $0$ following position $N-1$. A cow resides at each position. The cows are also numbered sequentially from $0$ to $N-1$. Initially, cow $i$ starts in position $i$. You are told a set of $K$ positions $0=A_1<A_2<\dots<A_K<N$ that are "active", meaning the cows in these positions are the next to move. In each minute of the dance, two things happen. First, the cows in the active positions rotate: the cow at position $A_1$ moves to position $A_2$, the cow at position $A_2$ moves to position $A_3$, and so on, with the cow at position $A_K$ moving to position $A_1$. All of these $K$ moves happen simultaneously, so the after the rotation is complete, all of the active positions still contain exactly one cow. Next, the active positions themselves shift: $A_1$ becomes $A_1+1$, $A_2$ becomes $A_2+1$, and so on (if $A_i = N-1$ for some active position, then $A_i$ circles back around to $0$). Please calculate the order of the cows after $T$ minutes of the dance. ## Input The first line contains three integers $N, K$ and $T$. The second line contains $K$ integers representing the initial set of active positions $A_1,A_2, \dots, A_K$. Recall that $A_1 = 0$ and that these are given in increasing order. ## Output Output the order of the cows after $T$ minutes, starting with the cow in position $0$, separated by spaces. [samples] ## Note For the example above, here are the cow orders and $A$ for the first four timesteps: ``` Initial, T = 0: order = [0 1 2 3 4], A = [0 2 3] T = 1: order = [3 1 0 2 4] T = 1: A = [1 3 4] T = 2: order = [3 4 0 1 2] T = 2: A = [2 4 0] T = 3: order = [2 4 3 1 0] T = 3: A = [3 0 1] T = 4: order = [1 2 3 4 0] ``` $1 \leq K \leq N \leq 2 \cdot 10^5$, $1\le T\le 10^9$. - Inputs 2-7: $N \leq 1000, T \leq 10000$. - Inputs 8-13: No additional constraints.

Samples

Input #1

5 3 4
0 2 3

Output #1

1 2 3 4 0

API Response (JSON)

{
  "problem": {
    "name": "[USACO23OPEN] Rotate and Shift B",
    "description": {
      "content": "**Note: The time limit for this problem is 4s, 2x the default.** To celebrate the start of spring, Farmer John's $N$ cows have invented an intriguing new dance, where they stand in a circle and re-or",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9185"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**Note: The time limit for this problem is 4s, 2x the default.**\n\nTo celebrate the start of spring, Farmer John's $N$ cows have invented an intriguing new dance, where they stand in a circle and re-or...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments