TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

貴育成了 3N+1 位賽馬娘,編號由 03N

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

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

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

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

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

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

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

也就是說,編號為 i 的賽馬娘在於時間 t 舉辦的賽跑中所能表現出的馬力是 it+max0a,b,cN,a+b+c=i(fa+gb+hc)

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

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

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

Input Format

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

第二行輸入 N+1 個整數,分別代表 f0fN

第三行輸入 N+1 個整數,分別代表 g0gN

第四行輸入 N+1 個整數,分別代表 h0hN

  • N3×105
  • 0fi,gi,hi109

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