Movie Theater

AtCoder

IDarc200_c

Time2000ms

Memory256MB

Difficulty—

You are given a positive integer $N$ and sequences of positive integers of length $N$: $L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N)$. It is guaranteed that $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ are all distinct. A movie theater has $N$ seats arranged in a row from left to right. The $i$\-th seat from the left is called seat $i$. $N$ people, numbered $1$ to $N$, visit this movie theater. You assign one seat to each person. Let $P_i$ be the seat assigned to person $i$. Then, person $i$ arrives at time $L_i$, crosses seats $1,2,\ldots,P_i-1$ to sit in seat $P_i$, and leaves at time $R_i$, crossing seats $1,2,\ldots,P_i-1$ to exit. The **dissatisfaction** of person $i$ is the number of times other people cross seat $P_i$ during the time interval from time $L_i$ to time $R_i$ (not including exactly $L_i$ and $R_i$). Find the lexicographically smallest permutation $P$ of $(1,2,\ldots,N)$ that minimizes the total dissatisfaction of all people from $1$ to $N$. You are given $T$ test cases, so find the answer for each. ## Constraints * $1\le T\le 500$ * $1\le N\le 500$ * $1\le L_i < R_i\le 2\times N$ * $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ are all distinct. * The sum of $N$ over all test cases is at most $500$. * All input values are integers. ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ Each test case is given in the following format: $N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$ [samples]

Samples

Input #1

Output #1

2 1 3
1 2 3 4
2 4 1 5 3 6

For the first test case, if we set $P=(2,1,3)$, the process proceeds as follows:

*   Time $1$: Person $1$ sits in seat $2$.
*   Time $2$: Person $2$ sits in seat $1$.
*   Time $3$: Person $2$ leaves seat $1$.
*   Time $4$: Person $3$ sits in seat $3$. Person $1$'s dissatisfaction increases by $1$.
*   Time $5$: Person $1$ leaves seat $2$.
*   Time $6$: Person $3$ leaves seat $3$.

The total dissatisfaction of all people in this case is $1$.
It is impossible to make the total dissatisfaction smaller than $1$, and furthermore, $P=(2,1,3)$ is lexicographically smallest among all $P$ with total dissatisfaction of $1$. Therefore, $P=(2,1,3)$ is the answer.
For the second test case, the total dissatisfaction of all people is $6$ for any permutation $P$.

API Response (JSON)

{
  "problem": {
    "name": "Movie Theater",
    "description": {
      "content": "You are given a positive integer $N$ and sequences of positive integers of length $N$: $L=(L_1,L_2,\\ldots,L_N),R=(R_1,R_2,\\ldots,R_N)$. It is guaranteed that $L_1,L_2,\\ldots,L_N,R_1,R_2,\\ldots,R_N$ ar",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc200_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a positive integer $N$ and sequences of positive integers of length $N$: $L=(L_1,L_2,\\ldots,L_N),R=(R_1,R_2,\\ldots,R_N)$. It is guaranteed that $L_1,L_2,\\ldots,L_N,R_1,R_2,\\ldots,R_N$ ar...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments