Editorial for TSOC '15 Contest 2 #5 - Bebiliths
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
In the problem, you are given a list of "triples". The main goal for the problem, to sort the triples or "bebiliths" based on certain conditions. We can store bebiliths as objects, this will make it easier for us to sort them.
struct spider {
int speed, venom, claw, ID;
bool operator < (const spider & other) const {
if (speed == other.speed) {
if (speed >= uniform_speed) {
if (claw == other.claw)
return ID > other.ID;
return claw < other.claw;
} else {
if (venom == other.venom)
return ID > other.ID;
return venom < other.venom;
}
}
return speed < other.speed;
}
};
In the code above, we took every possible option into consideration. This operator overload method will help us sort the bebiliths.
We sort and reverse the bebiliths because sorting results in ascending order, and to make things easier, we just reverse it.
We're scanning for the position of a bebilith in the sorted list, then outputting its original ID. Or the number of bebiliths that were inputted before it + 1.
Solving the problem is left as an exercise to the reader!
Comments
This is a minor concern but by reversing the signs in the operator<, we don't need to call std::reverse.
Time Complexity:
