F. xor-sum

Codeforces

IDCF10241F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are given four integers $n$, $m$, $s$, $x$. You should construct an array of size $n$, such that: 1)All elements are integers between 0 and $m$. 2)The sum of the array should be $s$. 3)The xor sum of the array should be $x$. Can you? The first line of input contains one integer $t$ $(1 <= t <= 10^5)$ which is the number of test cases. For each test case, the input will contain four integers $n$, $m$, $s$, $x$ $(1 <= n <= 10^5)$ $(0 <= m < 2^(30))$ $(0 <= s <= 10^(18))$ $(0 <= x < 2^(30))$. The sum of $n$ overall test cases will not exceed $3 times 10^5$. For each test case, if there were no way to construct the array, print $-1$; otherwise, print an array of size $n$ that satisfies the rules on a line. ## Input The first line of input contains one integer $t$ $(1 <= t <= 10^5)$ which is the number of test cases.For each test case, the input will contain four integers $n$, $m$, $s$, $x$ $(1 <= n <= 10^5)$ $(0 <= m < 2^(30))$ $(0 <= s <= 10^(18))$ $(0 <= x < 2^(30))$.The sum of $n$ overall test cases will not exceed $3 times 10^5$. ## Output For each test case, if there were no way to construct the array, print $-1$; otherwise, print an array of size $n$ that satisfies the rules on a line. [samples]

**Definitions** Let $ t \in \mathbb{Z}^+ $ be the number of test cases. For each test case $ k \in \{1, \dots, t\} $, given: - $ n_k \in \mathbb{Z}^+ $: length of array - $ m_k \in \mathbb{Z}_{\ge 0} $: upper bound on each element - $ s_k \in \mathbb{Z}_{\ge 0} $: required sum of array - $ x_k \in \mathbb{Z}_{\ge 0} $: required XOR sum of array **Constraints** 1. $ 1 \le t \le 10^5 $ 2. For each $ k $: - $ 1 \le n_k \le 10^5 $ - $ 0 \le m_k < 2^{30} $ - $ 0 \le s_k \le 10^{18} $ - $ 0 \le x_k < 2^{30} $ 3. $ \sum_{k=1}^t n_k \le 3 \times 10^5 $ **Objective** For each test case $ k $, determine if there exists an array $ A_k = (a_{k,1}, \dots, a_{k,n_k}) $ such that: - $ a_{k,i} \in \mathbb{Z} $ and $ 0 \le a_{k,i} \le m_k $ for all $ i \in \{1, \dots, n_k\} $ - $ \sum_{i=1}^{n_k} a_{k,i} = s_k $ - $ \bigoplus_{i=1}^{n_k} a_{k,i} = x_k $ If such an array exists, output one such array; otherwise, output $-1$.

API Response (JSON)

{
  "problem": {
    "name": "F. xor-sum",
    "description": {
      "content": "You are given four integers $n$, $m$, $s$, $x$. You should construct an array of size $n$, such that:  1)All elements are integers between 0 and $m$. 2)The sum of the array should be $s$. 3)The xo",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10241F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given four integers $n$, $m$, $s$, $x$.\n\nYou should construct an array of size $n$, such that: \n\n1)All elements are integers between 0 and $m$.\n\n2)The sum of the array should be $s$.\n\n3)The xo...",
      "is_translate": false,
      "language": "English"
    },
    {
      "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\\} $, given:  \n- $ n_k \\in \\mathbb{Z}^+ $: length of array  \n- $ m_k \\in \\mathbb{Z}_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments