SRM553 Div1 Easy(250) Suminator

Suminator

試しに0にしてみて、wantedResultになるなら0。そうでない場合、1個の数字は高々1回しか結果に足されないので、-1の箇所が足されるかどうかを調べる。足されないならば、ここで得られた結果とwantedResultが等しくなければいけない。足される場合、得られる結果がwantedResultより小さければ、-1を正整数に変えてwantedResultが得られる。

#include <vector>
#include <algorithm>
using namespace std;

long long eval( vector<long long> P )
{
    int n = (int)P.size();
    vector<long long> S(n+1,0);
    for ( int i=0; i<n; i++ )
        if ( P[i]==0 )
        {
            long long x = S.back();  S.pop_back();
            long long y = S.back();  S.pop_back();
            S.push_back(x+y);
        }
        else
        {
            S.push_back(P[i]);
        }
    return S.back();
}

class Suminator{public:
int findMissing( vector <int> program, int wantedResult )
{
    vector<long long> P(program.begin(),program.end());

    int p = int( find(P.begin(),P.end(),-1LL) - P.begin() );

    P[p] = 0;
    if ( eval(P)==wantedResult )
        return 0;

    long long INF = 1LL<<60;
    P[p] = INF;
    long long v = eval(P);
    if ( v<INF )
        return v==wantedResult ? 1 : -1;
    else
        return wantedResult>v-INF ? int(wantedResult-(v-INF)) : -1;
}};