TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

貴育成了 $3N+1$ 位賽馬娘,編號由 $0$ 到 $3N$ 。

賽馬娘們有三種主要的營養來源:白飯、漢堡排、紅蘿蔔。

編號為 $i$ 的賽馬娘在每餐都必定會食用總共 $i$ 份的白米飯、漢堡排、紅蘿蔔,而且每種餐點都一定會食用整數份。

編號為 $i$ 的賽馬娘在時間 $t$ 時(這裡的時間是相對時間,所以 $t$ 可能為任意實數)的固有馬力為 $it$ 。

若在時間 $t$ 舉辦一場賽跑,每位賽馬娘都會在時間 $t$ 前預先吃飽(即,貴會讓編號 $i$ 的賽馬娘任意食用白米飯、漢堡排、紅蘿蔔再讓她在時間 $t$ 參賽)。

一位賽馬娘食用了 $i$ 份白米飯就會在她當前的固有馬力之上額外獲得 $f_i$ 大小的馬力。

一位賽馬娘食用了 $i$ 份漢堡排就會在她當前的固有馬力之上額外獲得 $g_i$ 大小的馬力。

一位賽馬娘食用了 $i$ 份紅蘿蔔就會在她當前的固有馬力之上額外獲得 $h_i$ 大小的馬力。

也就是說,編號為 $i$ 的賽馬娘在於時間 $t$ 舉辦的賽跑中所能表現出的馬力是 $it+\max \limits_{0\leq a,b,c \leq N, a+b+c=i}{(f_a+g_b+h_c)}$ 。

在時間 $t$ 舉辦的賽跑的勝者,就是在時間 $t$ 時馬力最大的賽馬娘,若有不只一名賽馬娘達到最大的馬力,就會判定為沒有勝者。

貴想去特別關心那些從未取勝的賽馬娘,也就是說貴想知道那些無論在任何時間 $t$ 賽跑都無法取勝的賽馬娘們她們的編號。

請你告訴貴這個問題的答案吧!(你肯定不會讓貴失望的吧?)

Input Format

第一行輸入一個正整數 $N$,代表貴育成了 $3N+1$ 位賽馬娘。

第二行輸入 $N+1$ 個整數,分別代表 $f_0$ 到 $f_N$。

第三行輸入 $N+1$ 個整數,分別代表 $g_0$ 到 $g_N$。

第四行輸入 $N+1$ 個整數,分別代表 $h_0$ 到 $h_N$。

  • $N\leq 3\times 10^ 5$
  • $0\leq f_i,g_i,h_i \leq 10^ 9$

Output Format

第一行輸出一個整數 $M$ ,代表從未取勝的賽馬娘的個數。

第二行輸出 $M$ 個整數,代表所有從未取勝的賽馬娘的編號從小到大排序後的結果。

Sample Input 1

3
3 1 8 7
9 1 3 1
5 1 1 6

Sample Output 1

5
1 3 4 7 8

Sample Input 2

1
1 2
1 2
1 2

Sample Output 2

2
1 2

Hints

Problem Source

IOICamp 2021 Day5 pL

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~41 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2
35 1000 262144 65536 2
36 1000 262144 65536 2
37 1000 262144 65536 2
38 1000 262144 65536 2
39 1000 262144 65536 2
40 1000 262144 65536 2
41 1000 262144 65536 2