English · Original
Chinese · Translation
Formal · Original
Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of positive integers _A_ = \[_a_1, _a_2, ..., _a__n_\] and _B_ = \[_b_1, _b_2, ..., _b__n_\] of length _n_ each which he uses to ask people some quite peculiar questions.
To test you on how good are you at spotting inequality in life, he wants you to find an _"unfair"_ subset of the original sequence. To be more precise, he wants you to select _k_ numbers _P_ = \[_p_1, _p_2, ..., _p__k_\] such that 1 ≤ _p__i_ ≤ _n_ for 1 ≤ _i_ ≤ _k_ and elements in _P_ are distinct. Sequence _P_ will represent indices of elements that you'll select from both sequences. He calls such a subset _P_ _"unfair"_ if and only if the following conditions are satisfied: 2·(_a__p_1 + ... + _a__p__k_) is **greater** than the sum of all elements from sequence _A_, and 2·(_b__p_1 + ... + _b__p__k_) is **greater** than the sum of all elements from the sequence _B_. Also, _k_ should be smaller or equal to because it will be to easy to find sequence _P_ if he allowed you to select too many elements!
Mike guarantees you that a solution will always exist given the conditions described above, so please help him satisfy his curiosity!
## Input
The first line contains integer _n_ (1 ≤ _n_ ≤ 105) — the number of elements in the sequences.
On the second line there are _n_ space-separated integers _a_1, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — elements of sequence _A_.
On the third line there are also _n_ space-separated integers _b_1, ..., _b__n_ (1 ≤ _b__i_ ≤ 109) — elements of sequence _B_.
## Output
On the first line output an integer _k_ which represents the size of the found subset. _k_ should be less or equal to .
On the next line print _k_ integers _p_1, _p_2, ..., _p__k_ (1 ≤ _p__i_ ≤ _n_) — the elements of sequence _P_. You can print the numbers in any order you want. Elements in sequence _P_ should be distinct.
[samples]
Mike 一直思考社会不平等的严酷性。他对此如此着迷，以至于在解题时也会受到影响。目前，Mike 有两个长度均为 #cf_span[n] 的正整数序列 #cf_span[A = [a1, a2, ..., an]] 和 #cf_span[B = [b1, b2, ..., bn]]，他用它们向人们提出一些非常奇特的问题。
为了测试你对生活中不平等的敏锐洞察力，他希望你找到原序列的一个 _"不公平"_ 子集。更准确地说，他希望你选择 #cf_span[k] 个数字 #cf_span[P = [p1, p2, ..., pk]]，使得对于 #cf_span[1 ≤ i ≤ k]，有 #cf_span[1 ≤ pi ≤ n]，且 #cf_span[P] 中的元素互不相同。序列 #cf_span[P] 将表示你从两个序列中选取元素的下标。他称这样的子集 #cf_span[P] 为 _"不公平"_，当且仅当满足以下条件：#cf_span[2·(ap1 + ... + apk)] *大于* 序列 #cf_span[A] 中所有元素的和，且 #cf_span[2·(bp1 + ... + bpk)] *大于* 序列 #cf_span[B] 中所有元素的和。此外，#cf_span[k] 应小于或等于 ，因为如果允许你选择过多元素，找到序列 #cf_span[P] 就太容易了！
Mike 保证在上述条件下解一定存在，请帮助他满足好奇心！
第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 序列中元素的个数。
第二行有 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— 序列 #cf_span[A] 的元素。
第三行也有 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, ..., bn] (#cf_span[1 ≤ bi ≤ 109]) —— 序列 #cf_span[B] 的元素。
第一行输出一个整数 #cf_span[k]，表示所找到子集的大小。#cf_span[k] 应小于或等于 。
下一行输出 #cf_span[k] 个整数 #cf_span[p1, p2, ..., pk] (#cf_span[1 ≤ pi ≤ n]) —— 序列 #cf_span[P] 的元素。你可以按任意顺序输出这些数字。序列 #cf_span[P] 中的元素必须互不相同。
## Input
第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 序列中元素的个数。第二行有 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, ..., an] (#cf_span[1 ≤ ai ≤ 109]) —— 序列 #cf_span[A] 的元素。第三行也有 #cf_span[n] 个用空格分隔的整数 #cf_span[b1, ..., bn] (#cf_span[1 ≤ bi ≤ 109]) —— 序列 #cf_span[B] 的元素。
## Output
第一行输出一个整数 #cf_span[k]，表示所找到子集的大小。#cf_span[k] 应小于或等于 。下一行输出 #cf_span[k] 个整数 #cf_span[p1, p2, ..., pk] (#cf_span[1 ≤ pi ≤ n]) —— 序列 #cf_span[P] 的元素。你可以按任意顺序输出这些数字。序列 #cf_span[P] 中的元素必须互不相同。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of sequences $ A = (a_1, \dots, a_n) $ and $ B = (b_1, \dots, b_n) $.
Let $ S_A = \sum_{i=1}^n a_i $, $ S_B = \sum_{i=1}^n b_i $.
Let $ P = \{p_1, \dots, p_k\} \subseteq \{1, \dots, n\} $ be a subset of indices with distinct elements and $ k \leq \left\lceil \frac{n}{2} \right\rceil $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq a_i, b_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \leq k \leq \left\lceil \frac{n}{2} \right\rceil $
**Objective**
Find a subset $ P $ of size $ k \leq \left\lceil \frac{n}{2} \right\rceil $ such that:
$$
2 \sum_{i \in P} a_i > S_A \quad \text{and} \quad 2 \sum_{i \in P} b_i > S_B
$$
API Response (JSON)
{
"problem": {
"name": "D. Mike and distribution",
"description": {
"content": "Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of pos",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF798D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Mike has always been thinking about the harshness of social inequality. He's so obsessed with it that sometimes it even affects him while solving problems. At the moment, Mike has two sequences of pos...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Mike 一直思考社会不平等的严酷性。他对此如此着迷，以至于在解题时也会受到影响。目前，Mike 有两个长度均为 #cf_span[n] 的正整数序列 #cf_span[A = [a1, a2, ..., an]] 和 #cf_span[B = [b1, b2, ..., bn]]，他用它们向人们提出一些非常奇特的问题。\n\n为了测试你对生活中不平等的敏锐洞察力，他希望你找到原序列的一个 _\"不公平...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of sequences $ A = (a_1, \\dots, a_n) $ and $ B = (b_1, \\dots, b_n) $. \nLet $ S_A = \\sum_{i=1}^n a_i $, $ S_B = \\sum_{i=1}^n b_i $. \nLet $ P...",
"is_translate": false,
"language": "Formal"
}
]
}