HASHCODE_KRISH MURARKA

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
8.9 kB
43
Indexable
Never
/******************************
     AUTHOR KRISH MURARKA
*******************************/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll                 long long int
#define mod                1000000007
#define modulo             998244353
#define pie                3.141592653589793
#define popcount           __builtin_popcount     //used to count number of set bits in a integer
#define llpopcount         __builtin_popcountll   
#define parity             __builtin_parity // returns true(1) if number has odd parity i.e odd no of set bits
#define llparity           __builtin_parityll 
#define leadzero           __builtin_clz  //returns number of leading zeros of a 32 bit int 
#define llleadzero         __builtin_clzll // returns number of leading zero of a 64 bit int 
#define trailzero          __builtin_ctz  // returns number of trailing zero 
#define lltrailzero        __builtin_ctzll 
#define f                  first
#define s                  second
#define pb                 push_back
#define popb               pop_back
#define  to_low(s)         transform(s.begin(), s.end(), s.begin(), ::tolower);//convert string to lowercase
#define  to_up(s)          transform(s.begin(), s.end(), s.begin(), ::toupper);//convert string to uppercase
#define inf                (ll)(9223372036854775807)
#define rep(i,a,b)         for(int i=a;i<b;i++)
#define pll                pair<ll,ll>
#define ppl                pair<ll,pair<ll,ll>>
#define mem1(a)            memset(a,-1,sizeof(a))
#define mem0(a)            memset(a,0,sizeof(a))
#define maxHeap(T)         priority_queue <T>
#define minHeap(T)         priority_queue <T, vector<T>, greater<T>> 
#define fast               ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
#define deb(x)             cout<<#x<<" "<<x<<"\n"
#define uid(l,r)           uniform_int_distribution<int>(l,r); // to use auto temp= uid(l,r). int x= temp(rng); to generate from [L,R]
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;} // only use in equations like sum=max(sum,x)  its equivalent ot amax(sum,x) => sums is changed automatically
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}
template<typename T> using pbds =tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; // *s.find_by_order(x)=> xth element on 0 based indexing  , s.order_of_key(x) => no of elements strictly smaller
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
//----------------------------------STRESS TESTING  --------------------------------------
 #ifdef krish_murarka
    #include "debug.hpp"
#else
    #define debug(...)
    #define testcases(...)
#endif
void debugger(){
    #ifdef krish_murarka
        freopen("error/errorA.txt", "w", stderr);
    #else
    #endif
}

// --------------------------------------TO TAKE INPUT --------------------------------------
void read_input()
{
  #ifdef krish_murarka
  freopen("input/inputA.txt","r",stdin);
  freopen("output/outputA.txt","w",stdout);
  freopen("error/errorA.txt","w",stderr); 
  #endif

}

// --------------------------------------CODE STARTS ------------------------------------------
map<string,ll> empToid;
map<string,ll> prToid;
struct skill{
  string name;
  int level;
  
  skill(){
    cin>>name;
    cin>>level;
  }  
};
struct Employee{
   string name;
   int id;  
   int nSkills;
   int total_level;
   vector<skill> eSkill;
   Employee(int i){
    cin>>name;
    empToid[name]=i;
    id = i;
    cin>> nSkills;
    for(int i =0;i< nSkills; i++){
        eSkill.pb(skill());
        total_level+= eSkill[i].level;
    }
    
   }   
};
struct Project{
    string name;
    int Duration;
    int id;
    int score;
    int deadline;
    int nRoles;
    vector<skill> eSkill;
    Project(int i){
        cin>>name;
        cin>>Duration;
        cin>>score;
        cin>>deadline;
        cin>>nRoles;
        
        prToid[name] = i;
        id = i;
        for(int i=0;i<nRoles;i++){
            eSkill.pb(skill());
        }
    }
};
int nContributors,nProjects;
vector<Employee> employees;
vector<Project> projects;
vector<vector<string>> Assignments;
void printEmployeeDetails(){
    string statement = "THE EMPLOYEE DETAILS ARE : ";
    debug(statement);
    for(auto emp: employees){
      debug(emp.name);
      debug(emp.id);
      debug(emp.nSkills);
      for(auto sk: emp.eSkill){
        debug(sk.name);
        debug(sk.level);
      }
  }
}
void printProjectDetails(vector<Project> projects){
    string statement = "THE Project DETAILS ARE : ";
    debug(statement);
    for(auto pr: projects){
      debug(pr.name);
      debug(pr.Duration);
      debug(pr.score);
      debug(pr.deadline);
      debug(pr.nRoles);
      for(auto sk: pr.eSkill){
        debug(sk.name);
        debug(sk.level);
      }
  }
}
void PrintOutput(){
   cout<<Assignments.size()<<"\n";
   for(int i=0;i<Assignments.size();i++){
        cout<<Assignments[i][0]<<"\n";
      for(int j=1;j<Assignments[i].size();j++){
        cout<<Assignments[i][j]<<" ";
      }
      cout<<"\n";
   }
}
ll ScoreCalculator(vector<vector<string>> Assignments){
    
    ll workStart =0;
    ll curr_score =0;
    vector<ll> empTime(nContributors +1 ,0);
    for(int i=0;i<Assignments.size();i++){
       int prId = prToid[Assignments[i][0]];
       auto curr_project = projects[prId -1];
       
       int maxTime =0;
       for(int j=1;j<Assignments[i].size();j++){
          int empId = empToid[Assignments[i][j]];
          amax(maxTime,empTime[empId]);
       }

       ll expTime = maxTime + curr_project.Duration;
       ll delay = max(0LL,expTime - curr_project.deadline);
       
       curr_score += max(0LL,curr_project.score - delay);
       
       workStart = expTime;
       for(int j=1;j<Assignments[i].size();j++){
          int empId = empToid[Assignments[i][j]];
          empTime[empId] =workStart;
       }
    }
    return curr_score;   
}
void solving()
{
   
  cin>> nContributors >> nProjects;
  for(int i=1;i<=nContributors;i++){
      employees.pb(Employee(i));
  }
  
  for(int i=1;i<=nProjects;i++){
    projects.pb(Project(i));
  }
   vector<Project> pCopy = projects;
   sort(pCopy.begin(),pCopy.end(),[](Project& a, Project& b){
        // return a.deadline + a.Duration + a.score  < b.deadline + b.Duration + b.score;
        return  a.Duration - a.score   <  b.Duration - b.score;
        
   });
   
   vector<Employee> eCopy = employees;
   sort(eCopy.begin(),eCopy.end(),[](Employee& a, Employee& b){
    return a.total_level  > b.total_level;
   });
   ll maxi=0;
   for(int t=0;t<=1;t++){
       // random_shuffle(pCopy.begin(),pCopy.end());
       random_shuffle(eCopy.begin(),eCopy.end());
       vector<vector<string>> new_Assignments;
       for(int i=0;i<pCopy.size();i++){
            vector<string> temp;
            temp.pb(pCopy[i].name);
            random_shuffle(pCopy[i].eSkill.begin(),pCopy[i].eSkill.end());
            vector<bool> taken(nContributors+1,false);
            for(int j=0;j<pCopy[i].eSkill.size();j++){
                   string nm = pCopy[i].eSkill[j].name;
                   int reqSk =pCopy[i].eSkill[j].level;
                   bool hasSkill = false;
                   for(auto emp: eCopy){
                        int id = emp.id;
                        if(taken[id])continue;
                        
                        for(auto &sk : emp.eSkill){
                            if(sk.name == nm && sk.level >=reqSk){
                                hasSkill=true;
                                taken[id]=true;
                                temp.pb(emp.name);
                                if(reqSk == sk.level)
                                    sk.level++;
                                break;
                            }
                        }
                        if(hasSkill)break;
                   }
                   if(!hasSkill) break;
            }
            if(temp.size()-1 != pCopy[i].eSkill.size()){
                continue;
            }else{
                new_Assignments.pb(temp);
            }
       }
       
       ll x = ScoreCalculator(new_Assignments);
       if(x > maxi){
        maxi =x;
        Assignments = new_Assignments;
       }
   }
   
   
  debug(ScoreCalculator(Assignments));
  
  PrintOutput();
  



}

int main()
{
    fast;
    debugger();
    read_input();
    int t=1;
    // cin>>t; 
    for(int i=1;i<=t;i++)
    {  
     testcases("Case #",i);
    //cout<<"Case #"<<i<<": ";
     solving();

    }
   
    return 0;
}