F. Anton and School

Codeforces

IDCF734F

Time2000ms

Memory256MB

Difficulty—

bitmasksconstructive algorithmsimplementationmath

English · Original

Chinese · Translation

Formal · Original

Anton goes to school, his favorite lessons are arraystudying. He usually solves all the tasks pretty fast, but this time the teacher gave him a complicated one: given two arrays _b_ and _c_ of length _n_, find array _a_, such that: where _a_ _and_ _b_ means bitwise AND, while _a_ _or_ _b_ means bitwise OR. Usually Anton is good in arraystudying, but this problem is too hard, so Anton asks you to help. ## Input The first line of the input contains a single integers _n_ (1 ≤ _n_ ≤ 200 000) — the size of arrays _b_ and _c_. The second line contains _n_ integers _b__i_ (0 ≤ _b__i_ ≤ 109) — elements of the array _b_. Third line contains _n_ integers _c__i_ (0 ≤ _c__i_ ≤ 109) — elements of the array _c_. ## Output If there is no solution, print - 1. Otherwise, the only line of the output should contain _n_ non-negative integers _a__i_ — elements of the array _a_. If there are multiple possible solutions, you may print any of them. [samples]

Anton 去上学，他最喜欢的课程是数组学习。他通常很快就能解决所有题目，但这次老师给了他一个复杂的题目：给定两个长度为 #cf_span[n] 的数组 #cf_span[b] 和 #cf_span[c]，求一个数组 #cf_span[a]，使得：其中 #cf_span[a and b] 表示按位与，而 #cf_span[a or b] 表示按位或。 Anton 通常在数组学习方面很擅长，但这个问题太难了，因此他向你求助。输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000]) —— 数组 #cf_span[b] 和 #cf_span[c] 的大小。第二行包含 #cf_span[n] 个整数 #cf_span[bi] (#cf_span[0 ≤ bi ≤ 10^9]) —— 数组 #cf_span[b] 的元素。第三行包含 #cf_span[n] 个整数 #cf_span[ci] (#cf_span[0 ≤ ci ≤ 10^9]) —— 数组 #cf_span[c] 的元素。如果没有解，请输出 #cf_span[ - 1]。否则，输出仅一行，包含 #cf_span[n] 个非负整数 #cf_span[ai] —— 数组 #cf_span[a] 的元素。如果有多个可能的解，你可以输出其中任意一个。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000]) —— 数组 #cf_span[b] 和 #cf_span[c] 的大小。第二行包含 #cf_span[n] 个整数 #cf_span[bi] (#cf_span[0 ≤ bi ≤ 10^9]) —— 数组 #cf_span[b] 的元素。第三行包含 #cf_span[n] 个整数 #cf_span[ci] (#cf_span[0 ≤ ci ≤ 10^9]) —— 数组 #cf_span[c] 的元素。 ## Output 如果没有解，请输出 #cf_span[ - 1]。否则，输出仅一行，包含 #cf_span[n] 个非负整数 #cf_span[ai] —— 数组 #cf_span[a] 的元素。如果有多个可能的解，你可以输出其中任意一个。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 200{,}000 $. Let $ B = (b_1, b_2, \dots, b_n) $ and $ C = (c_1, c_2, \dots, c_n) $ be sequences of integers with $ 0 \leq b_i, c_i \leq 10^9 $. Let $ A = (a_1, a_2, \dots, a_n) $ be the target sequence of non-negative integers. **Constraints** For each $ i \in \{1, \dots, n\} $: $$ b_i = a_i \land a_{i+1}, \quad c_i = a_i \lor a_{i+1} $$ where indices are taken modulo $ n $, i.e., $ a_{n+1} = a_1 $. **Objective** Find any sequence $ A $ satisfying the above constraints for all $ i $, or output $-1$ if no such sequence exists.

Samples

Input #1

4
6 8 4 4
16 22 10 10

Output #1

3 5 1 1

Input #2

5
8 25 14 7 16
19 6 9 4 25

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "F. Anton and School",
    "description": {
      "content": "Anton goes to school, his favorite lessons are arraystudying. He usually solves all the tasks pretty fast, but this time the teacher gave him a complicated one: given two arrays _b_ and _c_ of length ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF734F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Anton goes to school, his favorite lessons are arraystudying. He usually solves all the tasks pretty fast, but this time the teacher gave him a complicated one: given two arrays _b_ and _c_ of length ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Anton 去上学，他最喜欢的课程是数组学习。他通常很快就能解决所有题目，但这次老师给了他一个复杂的题目：给定两个长度为 #cf_span[n] 的数组 #cf_span[b] 和 #cf_span[c]，求一个数组 #cf_span[a]，使得：\n\n其中 #cf_span[a and b] 表示按位与，而 #cf_span[a or b] 表示按位或。\n\nAnton 通常在数组学习方面很擅长，但...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 200{,}000 $.  \nLet $ B = (b_1, b_2, \\dots, b_n) $ and $ C = (c_1, c_2, \\dots, c_n) $ be sequences of integers with $ 0 \\leq b_i, c_i \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments