SRM553 Div1 Easy(250) 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; }};