Created
September 24, 2015 21:52
-
-
Save nomarlo/a090889ca2cc17123362 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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