Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.