solution to ova problem 10131

10131_bigger_smarter.cc

 #include<iostream>
 #include<vector>
 #include<algorithm>
 using namespace std;
 struct Elephant { 
   int iq,  weight, index;
   static bool iq_greater(const Elephant& e1, const Elephant& e2) {
     return e1.iq >= e2.iq;
   }
};

 void get_longest_seq(vector<Elephant>& elephants, vector<int>& seqCollector) {

   //loop invariant we know min ending point for seq of length 0 <= k < it
   int size = elephants.size();

   if(size == 0) return;
   vector<int> seqLengths = {0}; //seqLengths[i] smallest ending point of seq of length i
   vector<int> predecessor(size,-1); //predecessor[i] idx of predecessor i

   auto wt = [&elephants](const int i)  { return elephants[i].weight; };
   auto iq = [&elephants](const int i)  { return elephants[i].iq; };

   //loop invariant seqLenghts[0 .. i] we know bis of lengths 1 .. i+1
   //and predecessors of each idx
   int max_seq_size = 1;
   for(int i=1; i < size; i++) {
     if(wt(i) > wt(seqLengths.back()) and iq(i) < iq(seqLengths.back())) {
       predecessor[i] = seqLengths.back();
       seqLengths.push_back(i);
     }
     else if (wt(i) < wt(seqLengths[0])) {
	 seqLengths[0] = i;
     }
     else {
       auto it = lower_bound(seqLengths.begin()+1, seqLengths.end(), i, [&wt](int a, int b) {return wt(a) < wt(b); } );

       int j = it-seqLengths.begin();
       if(wt(seqLengths[j-1]) < wt(i) and iq(seqLengths[j-1]) > iq(i) ) {
	 seqLengths[j] = i;
	 predecessor[i] = seqLengths[j-1];
       }
     }

   }

  int current  = seqLengths.back();
  while(current != -1) {
    seqCollector.push_back(current);
    current = predecessor[current];
  }

}


void print_longest_seq_on(vector<Elephant>& elephants, vector<int>& seqCollector) {
  cout << seqCollector.size() << endl;
  for(auto it=seqCollector.rbegin(); it < seqCollector.rend(); it++){
    cout << elephants[*it].index << endl;
  }
  
}


int main() {

  vector<Elephant> elephants;
  vector<int> indices;
  vector<int> longest_seq;
  int i = 1;
  while(true)
    {
      Elephant ele;
      cin>>ele.weight;
      if (cin.fail()) break;
      cin >>ele.iq;
      ele.index = i++;
      elephants.push_back(ele);
    }	

  sort(elephants.begin(),elephants.end(), Elephant::iq_greater);
  get_longest_seq(elephants, longest_seq);
  print_longest_seq_on(elephants, longest_seq);

  return 0;
}