Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
solution to ova problem 10131
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment