Too Heavy

AtCoder

IDarc111_c

Time2000ms

Memory256MB

Difficulty—

There are $N$ people numbered $1$ to $N$ and $N$ pieces of baggage numbered numbered $1$ to $N$. Person $i$ has a weight of $a_i$, and Baggage $j$ has a weight of $b_j$. Initially, Person $i$ has Baggage $p_i$. We want to do the operation below zero or more times so that each Person $i$ will have Baggage $i$. * Choose $i,j (i \neq j)$, and swap the baggages of Person $i$ and Person $j$. However, when a person has a piece of baggage with a weight **greater than or equal to** his/her own weight, the person gets tired and becomes unable to take part in a future operation (that is, we cannot choose him/her as Person $i$ or $j$). Particularly, if $a_i \leq b_{p_i}$, Person $i$ cannot take part in any operation. Determine whether there is a sequence of operations that achieves the objective, and if so, construct one such sequence **with the minimum possible number of operations**. ## Constraints * $1 \leq N \leq 200000$ * $1 \leq a_i,b_i \leq 10^9$ * $p$ is a permutation of $1, \ldots, N$. * All numbers in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $a_2$ $\ldots$ $a_N$ $b_1$ $b_2$ $\ldots$ $b_N$ $p_1$ $p_2$ $\ldots$ $p_N$ [samples]

Samples

Input #1

Output #1

3
3 4
1 3
4 2

Initially, People $1, 2, 3, 4$ has pieces of baggage with weights $1, 3, 3, 5$, respectively, so no one is tired.
First, we do the operation choosing Person $3$ and $4$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $1, 3, 5, 3$, so no one is tired yet.
Second, we do the operation choosing Person $1$ and $3$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $5, 3, 1, 3$, so Person $1$ gets tired.
Lastly, we do the operation choosing Person $4$ and $2$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $5, 3, 1, 3$, so no one gets tired.
This sequence of operations has made everyone have the right piece of baggage, with the minimum possible number of operations, so it is valid.

Input #2

Output #2

\-1

No sequence of operations achieves the objective.

Input #3

Output #3

0

The objective is already achieved in the initial state.

API Response (JSON)

{
  "problem": {
    "name": "Too Heavy",
    "description": {
      "content": "There are $N$ people numbered $1$ to $N$ and $N$ pieces of baggage numbered numbered $1$ to $N$. Person $i$ has a weight of $a_i$, and Baggage $j$ has a weight of $b_j$. Initially, Person $i$ has Bagg",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc111_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ people numbered $1$ to $N$ and $N$ pieces of baggage numbered numbered $1$ to $N$. Person $i$ has a weight of $a_i$, and Baggage $j$ has a weight of $b_j$. Initially, Person $i$ has Bagg...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments