TopCoder SRM 144 Div 1 300 points

SRM_144_Div1_300.cpp

#include <vector>
#include <string>
#include <iostream>

using std::vector;
using std::string;

const string kNone = "NONE";

class BinaryCode {
 public:
  vector<string> decode(string message) {
    vector<string> ret;
    
    if( message.length() == 0 ) {
      ret.push_back(kNone);
      ret.push_back(kNone);
    } 
    else if ( message.length() == 1 ) {
      if( message[0] > '1' ) {
        ret.push_back(kNone);
        ret.push_back(kNone);
      } 
      else {
        if( message[0] == '0' ) {
          ret.push_back("0");
          ret.push_back(kNone);
        }
        else {
          ret.push_back(kNone);        
          ret.push_back("1");
        }
      }
    } 
    else {
      // Assume P[0] = 0
      ret.push_back( dec(message, "0") );
      
      // Assume P[0] = 1
      ret.push_back( dec(message, "1") );
    }
    
    return ret;
  }
  
 private:
  string dec(const string& message, string seed) {
    string P = seed;
      
    P += static_cast<char>(message[0] - P[0] + '0');
    
    if( P[1] < '0' || P[1] > '1' ) 
      return kNone;
     
    for(int i = 2; i < message.length(); ++i) {
      P += static_cast<char>(message[i-1] - (P[i-1] - '0') - (P[i-2] - '0') );
        
      if( P[i] > '1' || P[i] < '0' ) {
        break;
      }
    }
      
    if( message.length() == P.length() && (message[message.length()-1] == P[message.length()-2] + P[message.length()-1] - '0') )
	  return P;
    
    return kNone;
  }
};