C1. Yet Another Nim Game (Constructive version)

Codeforces

IDCFC1

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Alice and Bob decided to play the following game on $n$ piles of stones where the $i$-th$(1 <= i <= n)$ pile contains $p_i$ stones with Alice starting first : The player who cannot make a move loses. Note that both Alice and Bob are intelligent, so they always play optimally. Now your task is to *construct* any permutation$""^dagger$ $p$ of length $n$ such that the number of pairs ($l, r$)($1 <= l <= r <= n$), where Alice will win if both players play the game on piles $l, l + 1,..., r -1, r$, is *maximum* possible. $""^dagger$ A permutation is an array of length $n$, where each number from $1$ to $n$ appears exactly once. Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10000$). The description of the test cases follows. The first line of each test case contains a single integer $n$ ($1 <= n <= 3 dot.op 10^5$) — the number of piles. It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 dot.op 10^5$. For each test case, print $n$ integers — the required permutation $p$. If there are multiple answers, output any. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10000$). The description of the test cases follows.The first line of each test case contains a single integer $n$ ($1 <= n <= 3 dot.op 10^5$) — the number of piles.It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 dot.op 10^5$. ## Output For each test case, print $n$ integers — the required permutation $p$.If there are multiple answers, output any. [samples]

*这是该问题的简单版本，唯一的区别是不存在第三个限制*。给你一个整数 $n$。构造一个长度为 $2 n$ 的排列 $p$，使其满足：如果没有解，请输出 $-1$。输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^5)$，表示测试用例的数量。每个测试用例占一行。每个测试用例的唯一一行包含一个整数 $n (2 lt.eq n lt.eq 10^5)$。所有测试用例中 $n$ 的总和不超过 $10^5$。对于每个测试用例，在新的一行上输出一个满足上述限制的长度为 $2 n$ 的排列。如果没有解，请输出 $-1$。 ## Input 输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^5)$，表示测试用例的数量。每个测试用例占一行。每个测试用例的唯一一行包含一个整数 $n (2 lt.eq n lt.eq 10^5)$。所有测试用例中 $n$ 的总和不超过 $10^5$。 ## Output 对于每个测试用例，在新的一行上输出一个满足上述限制的长度为 $2 n$ 的排列。如果没有解，请输出 $-1$。 [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, t\} $, let $ n_k \in \mathbb{Z} $ be the input integer, and let $ P_k $ be a permutation of $ \{1, 2, \dots, 2n_k\} $. **Constraints** 1. $ 1 \le t \le 10^5 $ 2. For each $ k $, $ 2 \le n_k \le 10^5 $ 3. $ \sum_{k=1}^{t} n_k \le 10^5 $ **Objective** For each test case $ k $, find a permutation $ P_k = (p_1, p_2, \dots, p_{2n_k}) $ of $ \{1, 2, \dots, 2n_k\} $ such that: $$ \sum_{i=1}^{n_k} |p_i - p_{n_k + i}| = n_k $$ If no such permutation exists, output $ -1 $.

API Response (JSON)

{
  "problem": {
    "name": "C1. Yet Another Nim Game (Constructive version)",
    "description": {
      "content": "Alice and Bob decided to play the following game on $n$ piles of stones where the $i$-th$(1 <= i <= n)$ pile contains $p_i$ stones with Alice starting first : The player who cannot make a move loses.",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CFC1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice and Bob decided to play the following game on $n$ piles of stones where the $i$-th$(1 <= i <= n)$ pile contains $p_i$ stones with Alice starting first :\n\nThe player who cannot make a move loses....",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "*这是该问题的简单版本，唯一的区别是不存在第三个限制*。\n\n给你一个整数 $n$。构造一个长度为 $2 n$ 的排列 $p$，使其满足：\n\n如果没有解，请输出 $-1$。\n\n输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^5)$，表示测试用例的数量。\n\n每个测试用例占一行。\n\n每个测试用例的唯一一行包含一个整数 $n (2 lt.eq n lt.eq 10^5)$。所有测试...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, t\\} $, let $ n_k \\in \\mathbb{Z} $ be the input integer, and let $ P_k $ be a permutatio...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments