SRM 497 Div2 Medium

gistfile1.cpp

#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <sstream>
#include <stack>
#include <queue>
using namespace std;

typedef long long ll;

class PermutationSignature {
public:
  vector <int> reconstruct(string signature) {
      vector<bool> used(signature.size()+2,false);
      used[0]=true;
      vector<int> rank(signature.size()+1);
      int now=0;
      rank[0]=now;
      for(int i=1;i<=signature.size();i++){
          if(signature[i-1]=='I'){
              rank[i]=++now;
          }else{
              rank[i]=--now;
          }
      }
      vector<int> ret(signature.size()+1);
      for(int i=0;i<ret.size();i++){
          int at=1;
          int lefs=0,rigs=0;
          if(i+1<ret.size()&&rank[i]>rank[i+1]){
              rigs++;
              for(int j=i+1;j+1<rank.size();j++){
                  if(rank[j]>=rank[j+1])rigs++;
                  else break;
              }
          }
          for(int j=0;j<used.size();j++){
              if(!used[j]){
                  if(rigs>0)rigs--;
                  else{
                      ret[i]=j;
                      used[j]=true;
                      break;
                  }
              }
          }
      }
      return ret;
  }
  
};