CF Gym 100685E Epic Fail of a Genie

 传送门

E. Epic Fail of a Genie

time limit per test

0.5 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

Aladdin had found a new shiny lamp and has started polishing it with his hands. Suddenly a mysterious genie appeared from within and offered Aladdin to fulfill any of his three wishes. Genie had a very subtle humor that made Aladdin very sceptical about him. Aladdin didn't believe that genie was so powerful that could do anything he had wished and asked him to become a mouse. The genie did that without hesitation. Then Aladdin asked genie to become a mouse pad. Genie didn't like this kind of wish but had to submit. Finally Aladdin tested genie's abilities in math: he had to choose a nonempty subset giving the maximum product from the given set of numbers. Genie was shocked. Math was his Achilles' heel, however he was able to contact anyone on earth to help him. You are a secret weapon of the genie — help him solve the test and avoid this epic fail. This is the last chance for the genie: he'll be forever jailed in the lamp if his new master doesn't trust him.

Input

The first line of input contains an integer N (2 ≤ N ≤ 10⁴) — the cardinality of a set of numbers.

The second line of input contains N floating-point numbers with absolute value not more than 10⁶. The fractional part of each number does not contain more than two digits.

Output

The first line of the output should contain a single integer M — the total number of numbers that genie should choose from the set.

The second line of output should contain 1-based indexes of these numbers. Indexes must be sorted in ascending order. If multiple solutions exist please output the one with the minimal subset cardinality. If there are still several suitable solutions output any of them.

Examples

Input

7
1 3 0 -1 -2 0.5 3

Output

4
2 4 5 7

---

 

题目大意：

给出N个实数（绝对值不超过10^6，小数部分最多两位），从中选出若干个数使它们的乘积最大，按升序输出所选数的下标（1-based index）。如果有多种方案输出所选的数的数目最少的方案，如仍有多种方案任意输出一组。

Solution:

容易看出选数步骤/策略：

为描述方便，记所选数的（可重）集合为S，初始S为空, N个数的（可重）集合为A。

（1）大于1的全选

（2）对于负数，从小到大排序，每次考虑头两个（最小的两个），若它们的乘积大于1则选出，否则停止

（3）若S为空，在取两个负数(若可能）与取最大数之间择最优者； 否则结束。

---

总结：

这道题我WA了8发。原因是：

(1) 对于负数的选取策略（步骤(2)）我想错了

(2) 我把第三步细分了好几种情况，写得比较繁，bug百出。

另外，这道题还要注意精度，可以将输入的数乘100转成int来避免。

 

---

Implementation:

#include <bits/stdc++.h>
using namespace std;

const int N(1e4+5);
typedef long long LL;
vector<pair<int,int>> a;
vector<int> ans;

int main(){
    int n, y, ma=INT_MIN, p;
    double x;
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>x;
        y=100*x;
        if(y>100) ans.push_back(i);
        else{
            a.push_back({y, i});
            if(y>ma) p=i, ma=y;
        }
    }
    sort(a.begin(), a.end());
    for(int i=1; i<a.size() && a[i].first<0 && a[i-1].first<0 && (LL)a[i].first*a[i-1].first>10000; i+=2)
        ans.push_back(a[i-1].second), ans.push_back(a[i].second);
    if(!ans.size())
        if(a[0].first*a[1].first>ma*100)    //error-prone
            ans.push_back(a[0].second), ans.push_back(a[1].second);
        else ans.push_back(p);
    cout<<ans.size()<<endl;
    sort(ans.begin(), ans.end());
    for(int i=0; i<ans.size(); i++){
        if(i) putchar(' ');
        cout<<ans[i];
    }
    puts("");
    return 0;
}