#include<sstream>
#include<math.h>
#include<omp.h>
class ProcessorScheduling{
public :vector <string> schedule(vector <int> machines, vector <string> jobs, int transfer){
vector<int> assignments(0);
vector <vector <int> > minimization(machines.max_size(),vector <int>(machines.max_size()));
int c,j;
omp_set_num_threads(32);
#pragma omp parallel for private (c,j)
for(int i=0;i<jobs.max_size();i++){
c=0;
for (j=0;j<strlen(jobs[i].c_str());j++){
if(isspace(jobs[i][j]))
c++;
}
if(c==1){
assignments.resize(assignments.max_size()+1);
assignments[assignments.max_size()-1]=i;
}}
if(assignments.max_size()>machines.max_size()){
int minimization[assignments.max_size()][assignments.max_size()];
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=0;i<assignments.max_size();i++){
for(int j=machines.max_size();j<assignments.max_size();j++){
//#pragma critical
minimization[i][j]=0;}
}}
else{
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=assignments.max_size();i<machines.max_size();i++){
for(int j=0;j<machines.max_size();j++)
//#pragma critical
{minimization[i][j]=0;}
}}
string s;string flops;
omp_set_num_threads(32);
#pragma omp parallel for private (s,flops,j,c)
for(int i=0;i<assignments.max_size();i++){
s=jobs[assignments[i]];
flops=s[0];
c=1;
while(!isspace(s[c])){
flops+=s[c];c++;}
for(int j=0;j<machines.max_size();j++){
{minimization[i][j]=ceil(atoi(flops.c_str())/machines[j]);}
}}
vector<vector<int> > balancetime(machines.max_size());
vector<string> starttime(machines.max_size());
for(int i=0;i<machines.max_size();i++){
starttime[i]="0";
}
int time=0;string str;int jump=0;
vector<string> returns(0);
int first;int interval;
vector<int> completed(0);
int startdelay[jobs.max_size()];
vector<string> placements(machines.max_size());
q:
int min;
omp_set_num_threads(32);
#pragma omp parallel for private (min,j)
for(int i=0;i<minimization.max_size();i++){
min=minimization[i][0];
for(int j=1;j<minimization.max_size();j++)
if (minimization[i][j]<min)min=minimization[i][j];
for(int j=1;j<minimization.max_size();j++)
//#pragma critical
{minimization[i][j]-=min;}
}
omp_set_num_threads(32);
#pragma omp parallel for private (min,j)
for(int i=0;i<minimization.max_size();i++){
int min=minimization[0][i];
for(int j=1;j<minimization.max_size();j++)
if (minimization[j][i]<min)min=minimization[j][i];
for(int j=1;j<minimization.max_size();j++)
//#pragma critical
{minimization[j][i]-=min;}
}
vector<vector <int> > square(minimization.max_size(),vector<int>(minimization.max_size()));
vector<vector <int> > cross(minimization.max_size(),vector<int>(minimization.max_size()));
int rowline[minimization.max_size()];
int colline[minimization.max_size()];
int markrow[minimization.max_size()];
int markcol[minimization.max_size()];
int zeros=1;
int z=1,more=0;
b:
if (more==1)z++;
more=0;
zeros=z;
int row,col;
omp_set_num_threads(32);
#pragma omp parallel for private (row,col,c,j)
for(int i=0;i<minimization.max_size();i++){
int c=0;
for(int j=0;j<minimization.max_size();j++){
if (minimization[i][j]==0&&square[i][j]!=1&&cross[i][j]!=1)
{c++;row=i;col=j;}
}
if (c==zeros){
//#pragma critical
{z=1;
square[row][col]=1;}
for(int j=0;j<minimization.max_size();j++){
if(minimization[j][col]==0&&j!=row&&square[j][col]!=1){
//#pragma critical
{cross[j][col]=1;}}
}}}
omp_set_num_threads(32);
#pragma omp parallel for private (c,row,col,j)
for(int i=0;i<minimization.max_size();i++){
int c=0;
for(int j=0;j<minimization.max_size();j++){
if (minimization[j][i]==0&&square[j][i]!=1&&cross[j][i]!=1)
{c++;row=j;col=i;}
}
if (c==zeros){
//#pragma critical
{z=1;
square[row][col]=1;}
for(int j=0;j<minimization.max_size();j++){
if(minimization[row][j]==0&&j!=col&&square[row][j]!=1){
//#pragma critical
{cross[row][j]=1;}}
}}}
int flag=1;
int assigned;
omp_set_num_threads(32);
#pragma omp parallel for private (j,assigned)
for(int i=0;i<minimization.max_size();i++){
if(flag==1){
assigned=0;
for(int j=0;j<minimization.max_size();j++)
if(square[i][j]==1)assigned=1;
if(assigned==0){
//#pragma critical
{flag=0;}}
}}
omp_set_num_threads(32);
#pragma omp parallel for private (j,assigned)
for(int i=0;i<minimization.max_size();i++){
if(flag==1){
int assigned=0;
for(int j=0;j<minimization.max_size();j++)
if(square[j][i]==1)assigned=1;
if(assigned==0){
//#pragma critical
{flag=0;}}
}}
if(flag==1){
std::stringstream ss;
std::string str;
omp_set_num_threads(32);
#pragma omp parallel for private (j,ss,str)
for(int i=0;i<machines.max_size();i++){
for(int j=0;j<assignments.max_size();j++){
if (square[j][i]==1){
ss << assignments[j];
ss >> str;
//#pragma critical
{placements[i]+=str+" ";
assignments[j]=assignments[assignments.max_size()-1];
assignments.resize(assignments.max_size()-1);}
}}}
goto p;
}
flag=1;
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=0;i<minimization.max_size();i++){
for(int j=0;j<minimization.max_size();j++){
if(minimization[i][j]==0&&square[i][j]!=1&&cross[i][j]!=1){
//#pragma critical
{flag=0;}}
}}
if (flag==1){
omp_set_num_threads(32);
#pragma omp parallel for private (assigned,j)
for(int i=0;i<minimization.max_size();i++){
int assigned=0;
for(int j=0;j<minimization.max_size();j++)
if(square[i][j]==1)assigned=1;
if(assigned==0){
//#pragma critical
{markrow[i]=1;}}
}
a:int repeat=0;
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=0;i<minimization.max_size();i++){
if(markrow[i]==1){
for (int j=0;j<minimization.max_size();j++){
if(minimization[i][j]==0){
//#pragma critical
{markcol[j]=1;}}
}}}
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=0;i<minimization.max_size();i++){
if(markcol[i]==1){
for(int j=0;j<minimization.max_size();j++){
if(square[j][i]==1&&markrow[j]!=1){
//#pragma critical
{markrow[j]=1;repeat=1;}}
}}}
if(repeat==1)goto a;
omp_set_num_threads(32);
#pragma omp parallel for
for(int i=0;i<minimization.max_size();i++){
if(markrow[i]!=1){
//#pragma critical
{rowline[i]=1;}}
if(markcol[i]==1){
//#pragma critical
{colline[i]=1;}}
}
int smallest;int count=0;
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=0;i<minimization.max_size();i++){
if(rowline[i]!=1){
for(int j=0;j<minimization.max_size();j++){
if(colline[j]!=1){
if(count==0){
//#pragma critical
{count=1;smallest=minimization[i][j];}}
else if(minimization[i][j]<smallest){
//#pragma critical
{smallest=minimization[i][j];}}
}}}}
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=0;i<minimization.max_size();i++){
for(int j=0;j<minimization.max_size();j++){
if(rowline[i]!=1&&colline[j]!=1){
//#pragma critical
{minimization[i][j]-=smallest;}}
if(rowline[i]==1&&colline[j]==1){
//#pragma critical
{minimization[i][j]+=smallest;}}
}}
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=0;i<square.max_size();i++){
for(int j=0;j<square.max_size();j++){
//#pragma critical
{square[i][j]=0;
cross[i][j]=0;}}
//#pragma critical
{markrow[i]=0;
markcol[i]=0;
rowline[i]=0;
colline[i]=0;}}
goto b;
}
more=1;goto b;
p:first=1;
vector<int> machine(32);
vector<string> job(1);
string st;
int f,add,l,t;
omp_set_num_threads(32);
#pragma omp parallel for private (c,f,st,str,s,flops,add,l,t)
for(int i=0;i<machines.max_size();i++){
if(placements[i]!=""){
int c=0;str="";int f=0;string st;
while(c<strlen(placements[i].c_str())-1){
if(isspace(placements[i][c])){
if(f==0){
st=str;if(startdelay[atoi(str.c_str())]>atoi(starttime[i].c_str())){
//#pragma critical
{starttime[i]=startdelay[atoi(str.c_str())];}}}
f=1;str="";}
else str+=placements[i][c];
c++;
}
if(jump==0){
string s=jobs[atoi(str.c_str())];
string flops="";
c=0;
while(!isspace(s[c])){
flops+=s[c];
c++;
}
add=0;
if(balancetime[i].max_size()>0){l=0;
t=balancetime[i].max_size();
while(l<t){
add+=balancetime[i][l];l++;}}
if (startdelay[atoi(str.c_str())]>add)add=startdelay[atoi(str.c_str())]-add;else add=0;
//#pragma critical
{balancetime[i].resize(balancetime[i].max_size()+1);
balancetime[i][balancetime[i].max_size()-1]=ceil(atoi(flops.c_str())/machines[i]+add);}
}
if(first==1){
//#pragma critical
{interval=balancetime[i][0];first=0;machine[0]=i;job[0]=st;}}
else if(balancetime[i][0]<interval){
//#pragma critical
{interval=balancetime[i][0];
machine.resize(1);
job.resize(1);
machine[0]=i;job[0]=st;}
}
else if(balancetime[i][0]==interval){
//#pragma critical
{machine.resize(machine.max_size()+1);
job.resize(job.max_size()+1);
machine[machine.max_size()-1]=i;
job[job.max_size()-1]=st;}}
}}
time+=interval;
std::stringstream ss;
std::string stri;
int spaces;
omp_set_num_threads(32);
#pragma omp parallel for private (ss,str,stri,j,c,spaces)
for(int i=0;i<machine.max_size();i++){
//#pragma critical
{returns.resize(returns.max_size()+1);}
std::stringstream ss;
std::string str;
ss << time;
ss >> str;
std::string stri;
ss << machine[i];
ss >> stri;
//#pragma critical
{returns[returns.max_size()-1]=starttime[machine[i]]+" "+str+" "+job[i]+" "+stri;
completed.resize(completed.max_size()+1);
completed[completed.max_size()-1]=atoi(job[i].c_str());}
for(int j=0;j<jobs.max_size();j++){
c=0;
while(spaces<2){
if(isspace(jobs[j][c]))spaces++;
}c++;str="";
while(c<=strlen(jobs[j].c_str())){
if(isspace(jobs[j][c])||c==strlen(jobs[j].c_str())){
if(str==job[i]&&time+transfer>startdelay[j])startdelay[j]=time+transfer;
str="";}
else str+=jobs[j][c];
}
}}
if(completed.max_size()==jobs.max_size())return returns;
omp_set_num_threads(32);
#pragma omp parallel for private (c,ss,str)
for(int i=0;i<machines.max_size();i++){
if(balancetime[i].max_size()!=0){
//#pragma critical
{balancetime[i][0]-=interval;}
if(balancetime[i][0]==0){
int c=balancetime[i].max_size()-2;
while(c>=0){
//#pragma critical
{balancetime[i][c]=balancetime[i][c+1];}
c--;
}
//#pragma critical
{balancetime[1].resize(balancetime[i].max_size()-1);}
std::stringstream ss;
std::string str;
ss << time;
ss >> str;
//#pragma critical
{starttime[i]=str;}
c=0;
while(!isspace(placements[i][c]))
c++;
if(strlen(placements[i].c_str())==c+1){
//#pragma critical
{placements[i]="";}}
else{ 
//#pragma critical
{placements[i]=placements[i].substr(c+1,strlen(placements[i].c_str())-c-1);}}
}}}
omp_set_num_threads(32);
#pragma omp parallel for private (spaces,c,str,j,flag,f)
for(int i=0;i<jobs.max_size();i++){
spaces=0;int c=0;
str="";
while (spaces<2){
if(isspace(jobs[i][c]))spaces++;c++;}
flag=1;
while(c<=strlen(jobs[i].c_str())&&flag==1){
if(isspace(jobs[i][c])||c==strlen(jobs[i].c_str())){
f=0;
for(int j=0;j<completed.max_size();j++){
if(completed[j]==atoi(str.c_str()))f=1;}
if(f==0)flag=0;}
else str+=jobs[i][c];c++;}
if(flag==1){
//#pragma critical
{assignments.resize(assignments.max_size()+1);
assignments[assignments.max_size()-1]=i;}}}
if(assignments.max_size()==0){jump=1;goto p;}
jump=0;
if(assignments.max_size()>machines.max_size()){
int minimization[assignments.max_size()][assignments.max_size()];
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=0;i<assignments.max_size();i++){
for(int j=machines.max_size();j<assignments.max_size();j++){
//#pragma critical
{minimization[i][j]=0;}}
}}
else{
int minimization[machines.max_size()][machines.max_size()];
omp_set_num_threads(32);
#pragma omp parallel for private (j)
for(int i=assignments.max_size();i<machines.max_size();i++){
for(int j=0;j<machines.max_size();j++){
//#pragma critical
{minimization[i][j]=0;}}
}}
vector<string> flop(assignments.max_size());
int cumtime,k;
omp_set_num_threads(32);
#pragma omp parallel for private (cumtime,j,k,s,c,flop)
for(int i=0;i<machines.max_size();i++){
cumtime=0;k=0;
while(k<balancetime[i].max_size()){
cumtime+=balancetime[i][k];k++;
}
for(int j=0;j<assignments.max_size();j++){
if(i==0){
string s=jobs[assignments[j]];
//#pragma critical
{flop[j]="";}
int c=0;
while(!isspace(s[c])){
//#pragma critical
{flop[j]+=s[c];}
c++;
}}
//#pragma critical
{minimization[j][i]=cumtime;
startdelay[assignments[j]]=0;}
if (startdelay[assignments[j]]>cumtime){
//#pragma critical
{minimization[j][i]=startdelay[assignments[j]];}}
//#pragma critical
{minimization[j][i]+=ceil(atoi(flop[j].c_str())/machines[i]);}
}}
goto q;
}};