SRM 327 Div2 Hard

gistfile1.txt

int setbit(int x, int n){
  return x | 1 << n;
}

bool testbit(int x, int n){
  return (x & 1 << n) != 0;
}

void printbit(int x){
  for(size_t i = 0; i < sizeof(int) * 8; i++){
    if(i % 8 == 0 && i > 0) cout << " ";
    cout << testbit(x,i);
  }
}

int dp[51][1<<5];

class NiceOrUgly {
  string s;
  bool isVow (char c){
    return c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
  }

  int push(int k, bool b){
    int newk = 0;
    if(b) newk = setbit(newk,0);
    for(int i = 0; i < 4; i++){
      if(testbit(k,i)){
        newk = setbit(newk,i+1);
      }
    }
    //printbit(newk);
    return newk;
  }

  bool isUgly(int k, int maxn = 5){
    if(k == 31) return true;
    for(int j = 0; j < maxn; j++){
      int cnt = 0;
      for(int i = 0; i + j < maxn; i++){
        if(!testbit(k,i + j)){
          cnt++;
        }else{
          break;
        }
      }
      if(cnt >= 3) return true;
    }
    return false;
  }

  int rec(int i, int k){
    //debug(i,k,isUgly(k));
    if(i == s.size()){
      if(isUgly(k,min(5,(int)s.size()))) return dp[i][k] = 1;
      return dp[i][k] = 0;
    }
    if(dp[i][k] != -1) return dp[i][k];

    if(i >= 5 && isUgly(k)){
      return dp[i][k] = 1;
    }


    if(s[i] == '?'){
      int res2 = rec(i+1,push(k,false));
      int res3 = rec(i+1,push(k,true));
      //debug(i,res2,res3);
      if((res2 == 0 && res3 == 1) ||
         (res2 == 1 && res3 == 0) || 
         (res2 == 2 || res3 == 2) ){
        return dp[i][k] = 2;
      }else{
        return dp[i][k] = res2;
      }
    }else if(isVow(s[i])){
      return dp[i][k] = rec(i+1,push(k,false));
    }else{
      return dp[i][k] = rec(i+1,push(k,true));
    }
  }

public:
  string describe( string _s ) {
    s = _s;
    memset(dp,-1,sizeof dp);
    int res = rec(0,0);
    if(res == 1){
      return "UGLY";
    }else if(res == 0){
      return "NICE";
    }else{
      return "42";
    }
  }
};