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.

Author: bobhob314

In the problem, you are given a list of "triples". The main goal for the problem, to sort the triples or the "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;
                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.

std::sort(enemies, enemies + n);
std::reverse(enemies, enemies + n);

We sort and reverse the bebiliths because sorting results in smallest to biggest order, and to make things easier, we just reverse it.

scanf("%d", &q);
for(int i = 0; i < q; i++){
    scanf("%d", &pos);
    printf("%d\n", enemies[pos - 1].ID + 1);

Here's the output code, we're scanning for the position of a bebilith in the sorted list, and outputting its original ID. Or the number of bebiliths that were inputted before him + 1.

Solving the problem is left as an exercise to the reader!


  • 3
    OneYearOld  commented on Nov. 26, 2020, 8:22 p.m.

    This is a minor concern but by reversing the signs in the operator<, we don't need to call std::reverse.

    Time Complexity: O(NlogN + Q)