SRM527 Div2 Hard

950

class P8XCoinChangeAnother {
public:
  vector<long long> solve(int N, long long sum, long long cnt) 
  {
    vector<long long> ret(N, 0);

    ret[0] = sum;
    for (int i = 0; i + 1 < N; ++i) {
      ret[i + 1] = ret[i] / 2LL;
      ret[i] %= 2LL;
    }

    lli rem = cnt - accumulate(ALL(ret), 0LL);
    if (rem) {
      for (int i = N - 1; 0 < i; --i) {
        lli n = min(rem, ret[i]);
        ret[i] -= n;
        ret[i - 1] += n * 2LL;
        rem -= n;
      }
      for (int i = 0; i < N; ++i) {
        if (ret[i] < 0) return vector<lli>();
      }
                
      if (rem) return vector<lli>();
      return ret;
    }

    for (int i = 0; i < N; ++i) {
      sum -= ret[i] * (1LL << i);      
    }
    if (sum) return vector<lli>();
    return ret;
  }

};