Hierarchical Calculator [RUPC2018 Day3 B]

解法

https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day3/2752876

数が5種類しか無いのでそれぞれ考えてみる。
A[i]=0は0になってしまうので使わない
A[i]=1は数が変わらないので使わない
A[i]=2は数が大きくなるので絶対使う
これらは分かりやすい。
A[i]=-2は2つペアで使うと×4となり、大きくなるのでなるべくペアで使う。
A[i]=-2が奇数個の場合は、(-2)×(-1)とすることで×2を達成できる。
そのため、奇数個の場合は-1があればそれと一緒に使い、無いなら使わないことにする。
A[i]=-1は上の用途でしか使用せず、単体では使わない。
　
これを実装しよう。
use[i] := i番目の数を使うか
を用意し、これを作った後に答えを作ろう。
あとは、「cnt[x] := A[i]=xである要素の個数」も使用する。

int N, A[101];
int use[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    map<int, int> cnt;
    rep(i, 0, N) cnt[A[i]]++;

    // 2
    rep(i, 0, N) if (A[i] == 2) use[i] = 1;

    // -2
    int m2 = cnt[-2];
    if (m2 % 2 == 1) {
        if (0 < cnt[-1]) {
            rep(i, 0, N) if (A[i] == -1) {
                use[i] = 1;
                break;
            }
        } else m2--;
    }
    rep(i, 0, N) if (A[i] == -2 and m2) {
        use[i] = 1;
        m2--;
    }

    vector<int> ans;
    rep(i, 0, N) if (use[i]) ans.push_back(i + 1);
    
    int n = ans.size();
    printf("%d\n", n);
    rep(i, 0, n) printf("%d\n", ans[i]);
}