978 - Lemmings Battle! UVA.cpp

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

/**
Esta solución se basa en usar un multiset, he visto implementaciones propias de un multiset con un set + vector e incluso algunas 
con map, en este caso uso lo que provee STL

Notar que un multiset si tenemo algo como M: 25 30 30 50
Y damos M.erase(30) el resultado sera -> 25 50, es decir borrara los 2 30's

Para convertir un reverse_iterator a iterator usamos: --it.base();

**/


multiset <int> G,B;
int GT[100000] ,BT [100000] ;

int gt,bt; //contadores para saber cuantos elementos se van a insertar



int t,b,sg,sb,ax,pg,pb;
multiset<int>::reverse_iterator it;
multiset<int>::reverse_iterator it2;
int main(){


    scanf("%d",&t);

    while(t--){
        gt=bt=pg=pb=0;//Los puntos de cada especie
        scanf("%d %d %d",&b,&sg,&sb);
        for(int i=0;i<sg;i++){
            scanf("%d",&ax);
            G.insert(ax);
            pg+=ax;
        }

        for(int i=0;i<sb;i++){
            scanf("%d",&ax);
            B.insert(ax);
            pb+=ax;
        }

        while( !G.empty() && !B.empty() && pg!=pb ){
            gt=bt=0;

             it=G.rbegin(); it2=B.rbegin();

            for(int i=0;i<b && (!G.empty() && !B.empty());i++ ){
                it=G.rbegin();
                 it2=B.rbegin();
                if(*it>*it2){
                    GT[gt]=*it-*it2;
                    G.erase(--it.base());
                    B.erase(--it2.base());
                    gt++;
                }
                else if(*it<*it2){
                    BT[bt]=*it2-*it;
                    G.erase(--it.base());
                    B.erase(--it2.base());
                    bt++;
                }
                else{
                    G.erase(--it.base());
                    B.erase(--it2.base());
                }
            }
            //Los ordenamos solo para hacerlo mas eficiente
            sort(GT, GT+gt);
            sort(BT,BT+bt);

            G.insert (GT,GT+gt);//Agregamos los resultados de la batalla
            B.insert (BT,BT+bt);
        }

        if(pg==pb){
            printf("green and blue died\n");
            G.clear();
            B.clear();
        }
        else if(!G.empty()){
            printf("green wins\n");
            for(it=G.rbegin();it!=G.rend();++it)
                printf("%d\n",*it);
            G.clear();
        }
        else if(!B.empty()){
            printf("blue wins\n");
            for(it=B.rbegin();it!=B.rend();++it)
                printf("%d\n",*it);
           B.clear();
        }
        else{
            printf("green and blue died\n");
        }

        if(t)
            printf("\n");

    }

    return 0;

}