hashcode-2022.cpp

#include <bits/stdc++.h>


using namespace std;

int C,P;

struct projectStruct{
    string name;
    int days;
    int score;
    int deadline;
    int roles;
    vector<pair<int,int>> skills;
};

vector<string> ppl;
vector<projectStruct> projects;

map<string,int> projectNames;

map <string,int> skills;
map<int,string> skills_rev;

vector<vector<int>> pplData;

vector<int> skillPpl[10000];

int busyPeeps[100000];

int currentSkill = 0;
//skillppl comparator
//sort with level
bool cmp(int a,int b){
    return pplData[a][currentSkill] < pplData[b][currentSkill];
}

//custom comparator for projects
bool cmpProject(projectStruct a,projectStruct b){
    return a.deadline < b.deadline;
}

//custom comparator for foundPeeps
bool cmpFoundPeeps(int a,int b){
    return busyPeeps[a]<busyPeeps[b];
}

void solve(){
    cin >> C >> P;
    int skillCount,projectCount;
    for(int i=0;i<C;i++){
        string s;
        cin >> s;
        ppl.push_back(s);
        int n;
        cin >> n;
        pplData.push_back(vector<int>(1000));
        //ppl input
        while(n--){
            string skill;
            cin >> skill;
            if(skills.find(skill)==skills.end()){
                skills[skill]=skillCount;
                skills_rev[skillCount] = skill;
                skillCount++;
            }
            int level;
            cin >> level;
            pplData[i][skills[skill]] = level;
            skillPpl[skills[skill]].push_back(i);
        }
    }

    for(int i=0;i<P;i++){
        string name;
        cin >> name;
        projectNames[name] = i;
         int days,score,roles,deadline;
        cin >> days >> score >> deadline >> roles;
        projectStruct p;
        p.name = name;
        p.days = days;
        p.score = score;
        p.deadline = deadline;
        p.roles = roles;

        for(int j=0;j<roles;j++){
            string skill;
            cin >> skill;
            int level;
            cin >> level;
            if(skills.find(skill)==skills.end()){
                skills[skill]=skillCount;
                skills_rev[skillCount] = skill;
                skillCount++;
            }
            p.skills.push_back(make_pair(skills[skill],level));
        }
        projects.push_back(p);
    }

    
    //sort skillPpl by level
    for(int i=0;i<skillCount;i++){
        currentSkill = i;
        sort(skillPpl[i].begin(),skillPpl[i].end(),cmp);
    }
    
    sort(projects.begin(),projects.end(),cmpProject);

    //input is done
    //solve the problem
    vector<int> ans;
    vector<vector<int>> ansData;
    //for each project
    for(int q=0;q<P;q++){
        string wantedName;
        cin >> wantedName;
        int i = projectNames[wantedName];
        vector<int> candidates;
        //for each skill
        vector<int> foundSkills(1000,0);
        for(pair<int,int> skill : projects[i].skills){
            if(skillPpl[skill.first].size()==0){
                //no one has this skill
                break;
            }
            //find the first person who has this skill
            vector<int> foundPeep;
            for(int currentPeep = 0;currentPeep<skillPpl[skill.first].size();currentPeep++){
                int pplIndex = skillPpl[skill.first][currentPeep];
                //check if this person can do this project
                if(pplData[pplIndex][skill.first]<skill.second){
                    //cant do this project
                    continue;
                }
                //check if this person is already in the candidates
                bool found = false;
                for(int j=0;j<candidates.size();j++){
                    if(candidates[j]==pplIndex){
                        found = true;
                        break;
                    }
                }
                if(found)
                    continue;
                foundPeep.push_back(skillPpl[skill.first][currentPeep]);
            }
            if(foundPeep.size()==0)break;
            sort(foundPeep.begin(),foundPeep.end(),cmpFoundPeeps);
            int chosenOne = foundPeep[0];
            //for each needed skill
            for(pair<int,int> neededSkill : projects[i].skills){
                if(pplData[chosenOne][neededSkill.first]>=neededSkill.second){
                    //will mentor this skill
                    foundSkills[neededSkill.first]=1;
                }
            }
            candidates.push_back(foundPeep[0]);
        }
        if(candidates.size()==projects[i].roles){
            //all candidates are good
            //get the project
            ans.push_back(i);
            ansData.push_back(candidates);
            for(int k=0;k<candidates.size();k++){
                int peep = candidates[k];
                if(pplData[peep][projects[i].skills[k].first]<=projects[i].skills[k].second){
                    pplData[peep][projects[i].skills[k].first]++;
                }
            }
        }
    }
    cout << ans.size() << endl;
    for(int i=0;i<ans.size();i++){
        cout << projects[ans[i]].name << "\n";
        for(int j=0;j<ansData[i].size();j++){
            cout << ppl[ansData[i][j]] << " ";
        }
        cout << "\n";
    }
}

int main(){
    solve();
}