Untitled
unknown
plain_text
2 years ago
2.4 kB
7
Indexable
#include <iostream>
#include <unordered_map>
#include <set>
#include <string>
using namespace std;
struct node{
int curtime;
int end;
int curOp;
int ops;
int maxP;
} pool[30005];
struct cmp{
bool operator()(const int x, const int y){
if(pool[x].end==pool[y].end) return x<y;
else return pool[x].end<pool[y].end;
}
};
int cnt, idx;
int n;
unordered_map<string,int> mymap;
set<int, cmp> s;
void init(int mProcessors)
{
cnt=0;
idx=0;
n=mProcessors;
mymap.clear();
s.clear();
}
void addProcessors(int timestamp, int mProcessors);
void update(int timestamp){
while(s.size()>0&&pool[*s.begin()].end<timestamp){
int it=*s.begin();
s.erase(s.begin());
addProcessors(pool[it].end,pool[it].curOp);
}
}
void change(int timestamp){
while (n && idx < cnt)
{
while (pool[idx].curOp >= pool[idx].maxP)
{
idx++;
if (idx >= cnt)
return;
}
int numOp = n;
if (numOp > (pool[idx].maxP - pool[idx].curOp))
numOp = pool[idx].maxP - pool[idx].curOp;
pool[idx].ops -= (pool[idx].curOp * (timestamp - pool[idx].curtime));
if (pool[idx].ops <= 0)
{
pool[idx].ops = 0;
idx++;
continue;
}
pool[idx].curOp += numOp;
n -= numOp;
pool[idx].curtime = timestamp;
s.erase(idx);
pool[idx].end = timestamp + pool[idx].ops / pool[idx].curOp;
if (pool[idx].ops %pool[idx].curOp)
pool[idx].end++;
s.insert(idx);
}
}
void newTask(int timestamp, char mTask[], int mOperations, int mMaxProes)
{
update(timestamp);
mymap[mTask]=cnt;
pool[cnt].curtime=timestamp;
pool[cnt].curOp=0;
pool[cnt].end=999999;
pool[cnt].maxP=mMaxProes;
pool[cnt].ops=mOperations;
cnt++;
change(timestamp);
}
void addProcessors(int timestamp, int mProcessors)
{
update(timestamp);
n+= mProcessors;
change(timestamp);
}
int getTaskOperations(int timestamp, char mTask[])
{
int id=mymap[mTask];
update(timestamp);
int ret=pool[id].ops-pool[id].curOp*(timestamp-pool[id].curtime);
change(timestamp);
if(ret>0) return ret;
return 0;
}Editor is loading...