Swap Many Times

AtCoder

IDabc253_g

Time2000ms

Memory256MB

Difficulty—

For an integer $N$ greater than or equal to $2$, there are $\frac{N(N - 1)}{2}$ pairs of integers $(x, y)$ such that $1 \leq x \lt y \leq N$. Consider the sequence of these pairs sorted in the increasing lexicographical order. Let $(x_1, y_1), \dots, (x_{R - L + 1}, y_{R - L + 1})$ be its $L$\-th, $(L+1)$\-th, $\ldots$, and $R$\-th elements, respectively. On a sequence $A = (1, \dots, N)$, We will perform the following operation for $i = 1, \dots, R-L+1$ in this order: * Swap $A_{x_i}$ and $A_{y_i}$. Find the final $A$ after all the operations. We say that $(a, b)$ is smaller than $(c, d)$ in the lexicographical order if and only if one of the following holds: * $a \lt c$ * $a = c$ and $b \lt d$ ## Constraints * $2 \leq N \leq 2 \times 10^5$ * $1 \leq L \leq R \leq \frac{N(N-1)}{2}$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $L$ $R$ [samples]

Samples

Input #1

5 3 6

Output #1

5 1 2 3 4

Consider the sequence of pairs of integers such that $1 \leq x \lt y \leq N$ sorted in the increasing lexicographical order. Its $3$\-rd, $4$\-th, $5$\-th, and $6$\-th elements are $(1, 4), (1, 5), (2, 3), (2, 4)$, respectively.
Corresponding to these pairs, $A$ transitions as follows.
$(1, 2, 3, 4, 5) \rightarrow (4, 2, 3, 1, 5) \rightarrow (5, 2, 3, 1, 4) \rightarrow (5, 3, 2, 1, 4) \rightarrow (5, 1, 2, 3, 4)$

Input #2

10 12 36

Output #2

1 10 9 8 7 4 3 2 5 6

API Response (JSON)

{
  "problem": {
    "name": "Swap Many Times",
    "description": {
      "content": "For an integer $N$ greater than or equal to $2$, there are $\\frac{N(N - 1)}{2}$ pairs of integers $(x, y)$ such that $1 \\leq x \\lt y \\leq N$. Consider the sequence of these pairs sorted in the increas",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc253_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "For an integer $N$ greater than or equal to $2$, there are $\\frac{N(N - 1)}{2}$ pairs of integers $(x, y)$ such that $1 \\leq x \\lt y \\leq N$.\nConsider the sequence of these pairs sorted in the increas...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments