//C++ STL header
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
bool desc(int a, int b)
{
return a >= b;
}
vector<int> solution(vector<string> genres, vector<int> plays) {
int size;
int count=0;
int genres_num[100000];
//장르 sort
map<string,bool> check;
map<string,map<int,int> > lotate_count;
string name[1000];
//이름저장
vector<int> answer;
map<int,string> play_and_genres;
//횟수별 장르
map<string,int> total_plays;
//장르별 들었던 횟수
map<string,vector<int> > genres_song;
//장르 내 노래
map<string,map<int,map<int,int> > > lotate;
//식별 번호
int i,j;
for(i = 0; i < genres.size();i++)
{
lotate[genres[i]][plays[i]][lotate_count[genres[i]][plays[i]]]=i;
lotate_count[genres[i]][plays[i]]++;
genres_song[genres[i]].push_back(plays[i]);
total_plays[genres[i]]+=plays[i];
if(!check[genres[i]])
{
check[genres[i]]=true;
name[count]=genres[i];
count++;
}
}
lotate_count.clear();
for(i = 0;i < count;i++)
{
genres_num[i]=total_plays[name[i]];
play_and_genres[total_plays[name[i]]]=name[i];
}
sort(genres_num,genres_num+count,desc);
for(i = 0;i < count;i++)
{
sort(genres_song[play_and_genres[genres_num[i]]].begin(),genres_song[play_and_genres[genres_num[i]]].end(),desc);
size = genres_song[play_and_genres[genres_num[i]]].size();
if(size == 1)
{
for(j = 0;j < 1;j++)
{
answer.push_back(lotate[play_and_genres[genres_num[i]]][genres_song[play_and_genres[genres_num[i]]][j]][lotate_count[play_and_genres[genres_num[i]]][genres_song[play_and_genres[genres_num[i]]][j]]]);
}
}
else
{
for(j = 0;j < 2;j++)
{
answer.push_back(lotate[play_and_genres[genres_num[i]]][genres_song[play_and_genres[genres_num[i]]][j]][lotate_count[play_and_genres[genres_num[i]]][genres_song[play_and_genres[genres_num[i]]][j]]]);
lotate_count[play_and_genres[genres_num[i]]][genres_song[play_and_genres[genres_num[i]]][j]]++;
}
}
}
return answer;
}