HASHCODE_KRISH MURARKA
unknown
c_cpp
3 years ago
8.9 kB
45
Indexable
/******************************
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;
}
Editor is loading...