[语言月赛 202410] 同桌

Luogu

IDLGB4045

Time1000ms

Memory512MB

DifficultyP1

2024数组语言月赛

一个班级内有 $2n$ 个小朋友，编号依次为 $1,2,\ldots, 2n$。教室里有 $n$ 张桌子，每张桌子可以坐两个人。坐在同一张桌子旁边的小朋友互为同桌。**一个小朋友的同桌不能是自己。** 老师问每个小朋友想和谁做同桌，$i$ 号小朋友的回答是想和 $p_i$ 号小朋友做同桌。请你帮老师判断一下，老师能否让每个小朋友都满意？ ## Input 输入的第一行有一个正整数 $n$，表示桌子的张数。第二行有 $2n$ 个数 $p_1,p_2,\ldots,p_{2n}$，表示每个小朋友想和谁做同桌。 ## Output 如果老师可以让所有小朋友都满意，则输出 `Yes`，否则输出 `No`。 [samples] ## Note 【样例 1 解释】老师可以让 $1,2$ 号小朋友坐在一张桌子旁，$3,6$ 号小朋友坐在第二张桌子旁，$4,5$ 坐在第三张桌子旁。【样例 2 解释】 $1$ 号小朋友的同桌肯定不会是自己（因为每张桌子一定恰好坐 $2$ 个小朋友）。【样例 3 解释】 $1$ 号小朋友想和 $2$ 号小朋友做同桌，然而 $2$ 号小朋友却希望和 $3$ 号小朋友做同桌，所以不可能 $1,2$ 号小朋友同时满意。如果你进一步思考会发现，老师最多同时让 $2$ 个小朋友满意。【数据范围】 **本题采用捆绑测试，一个子任务内有多个测试点，同时答对子任务内所有测试点才能拿到对应分数**。 - 子任务 1（$9$ 分）：$n=1$。 - 子任务 2（$12$ 分）：$n=2$。 - 子任务 3（$28$ 分）：保证 $p_i\ne i$。 - 子任务 4（$51$ 分）：无特殊限制。对于全体数据，保证 $1\le n\le 5000$，$1\le p_i\le 2n$。

Samples

Input #1

3
2 1 6 5 4 3

Output #1

Yes

Input #2

2
1 2 4 3

Output #2

No

Input #3

2
2 3 4 1

Output #3

No

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛 202410] 同桌",
    "description": {
      "content": "一个班级内有 $2n$ 个小朋友，编号依次为 $1,2,\\ldots, 2n$。教室里有 $n$ 张桌子，每张桌子可以坐两个人。坐在同一张桌子旁边的小朋友互为同桌。**一个小朋友的同桌不能是自己。** 老师问每个小朋友想和谁做同桌，$i$ 号小朋友的回答是想和 $p_i$ 号小朋友做同桌。 请你帮老师判断一下，老师能否让每个小朋友都满意？",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4045"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个班级内有 $2n$ 个小朋友，编号依次为 $1,2,\\ldots, 2n$。教室里有 $n$ 张桌子，每张桌子可以坐两个人。坐在同一张桌子旁边的小朋友互为同桌。**一个小朋友的同桌不能是自己。**\n\n老师问每个小朋友想和谁做同桌，$i$ 号小朋友的回答是想和 $p_i$ 号小朋友做同桌。\n\n请你帮老师判断一下，老师能否让每个小朋友都满意？\n\n## Input\n\n输入的第一行有一个正整数 $n$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments