| Time Limit: 20000MS | Memory Limit: 65536K | |
| Total Submissions: 1165 | Accepted: 110 | |
| Case Time Limit: 5000MS | ||
Description
This is a multitask OS, processes run at the same time. There are following command in the OS:
CreateProcess(PID,Memory,Priority)
A new process is created with the process identification PID and
memory size, and a priority. The priority in this command is called
outer priority of a process.
AddMessage(PID,Priority)
That means, add a new message to the message queue of process PID,
with the priority of Priority. The message with higher Priority will run
earlier that lower ones. The Priority is called inner priority.
Run
Find out the message with biggest HP. HP is defined as the product
of the inner priority of a message and the corresponding process
priority. If two or more messages have the same HP, the one with
smallest PID will run first. Print the information "Run: HP" to the
output file, HP will be replaced by the message HP you found, or print
"Empty" instead if the message queue is empty. Finally remove this
message if exist.
ChangePriority(PID,NewValue)
Change the outer priority of process PID to NewValue.
GetMemory(PID,Memory)
Process PID memory increases the amount of Memory.
FreeMemory(PID,Memory)
Process PID memory decreases the amount of Memory.
RunProcess(PID)
Similar with Run command. Find out the message in the process PID
message queue, print the information "Run Process: Priority" to the
output file, Priority will be replaced by the message priority you
found, or print "Empty" instead if the message queue is empty. Finally
remove this message if exist.
CloseMaxMemory
Find out the process that used the largest number of memory and
close it if exists (if tie, the one with smallest PID should be release
first), or print "Empty" instead.
CloseProcess(PID)
Close the process with the identification of PID.
Whenever a process' memory is less than or equal to 0, it will be
close automatically. In any of the above commands except the first one,
if the PID doesn't exist, please print an "Error" to the output. For the
first command, if the PID is already exist, print an "Error" and ignore
this command.
Input
line in the input is an integer number N (1 <= N <= 100000),
which represents the number of commands. The next N lines, each gives a
command described above. Any number given in the input file will be
non-negative integer and will not be more than 1000000000.
Output
Sample Input
11
CloseMaxMemory
CreateProcess(1,100,1)
CreateProcess(2,200,1)
CreateProcess(3,300,1)
AddMessage(1,9)
AddMessage(2,19)
AddMessage(1,10)
GetMemory(2,999)
CloseMaxMemory
Run
RunProcess(1)
Sample Output
Empty
Run: 10
Run Process: 9
Hint
Source
POJ上又一个通过率较低的模拟题，还有一个是POJ 1025 Department。
CreateProcess(PID,Memory,Priority)
CreatProcess(PID, Memory, Priority)操作中Memory可能为零（Any number given in the input file will be non-negative integer）。
Implementation:
#include <cstdio>
#include <set>
#include <map>
#include <queue>
#define LL long long
#define MEM second
#define PRO first
#define PID first
#define HP second
using namespace std; const int N(1e5+);
priority_queue<int> que[N]; typedef pair<int,LL> P; map<int,P> mp;
map<int,int> ID; bool cmp(const P &a, const P &b){
return a.second!=b.second?a.second>b.second:a.first<b.first;
} set<P, bool(*)(const P &, const P &)> o(cmp), m(cmp); void Erase(int pid){
int id=ID[pid];
if(que[id].size()){
o.erase(P(pid, (LL)que[id].top()*mp[pid].PRO));
que[id].pop();
}
} void remove_process(int pid){
Erase(pid);
m.erase(P(pid, mp[pid].MEM));
int id=ID[pid];
for(; que[id].size(); que[id].pop());
mp.erase(pid);
} void Insert(int pid){
int id=ID[pid];
if(que[id].size()){
o.insert(P(pid, (LL)que[id].top()*mp[pid].PRO));
}
} void close_process(int pid){
if(mp.find(pid)==mp.end()) puts("Error");
else remove_process(pid);
} void close_max_memory(){
if(m.empty()) puts("Empty");
else remove_process(m.begin()->PID); //error-prone
} void run_process(int pid){
if(mp.find(pid)==mp.end()){
puts("Error");
return;
}
int id=ID[pid];
if(que[id].empty()) puts("Empty");
else{
printf("Run Process: %d\n", que[id].top());
Erase(pid), Insert(pid);
}
} void modify_memory(int pid, int mem){
if(mp.find(pid)==mp.end()){
puts("Error");
return;
}
if(mp[pid].MEM+mem<=)
remove_process(pid);
else{
P now=mp[pid];
m.erase(P(pid, now.MEM));
m.insert(P(pid, now.MEM+mem));
mp[pid].MEM+=mem;
}
} void change_priority(int pid, int pro){
if(mp.find(pid)==mp.end()){
puts("Error");
return;
}
int id=ID[pid];
if(que[id].size()){
int i_pro=que[id].top();
o.erase(P(pid, (LL)mp[pid].PRO*i_pro));
o.insert(P(pid, (LL)pro*i_pro));
}
mp[pid].PRO=pro;
} void run(){
if(o.empty()) puts("Empty");
else{
printf("Run: %lld\n", o.begin()->HP);
int pid=o.begin()->PID;
Erase(pid), Insert(pid);
}
} void add_message(int pid, int pro){
if(mp.find(pid)==mp.end()){
puts("Error");
return;
}
int id=ID[pid];
if(que[id].size()){
int i_pro=que[id].top();
o.erase(P(pid, (LL)i_pro*mp[pid].PRO));
}
que[id].push(pro);
o.insert(P(pid, (LL)que[id].top()*mp[pid].PRO));
} int tail; void create_process(int pid, int mem, int pro){
if(mp.find(pid)!=mp.end()){
puts("Error");
return;
}
if(mem){
mp[pid]=P(pro, mem);
m.insert(P(pid, mem));
ID[pid]=tail++;
}
} char s[]; int main(){
int n, pid, mem, pro;
for(scanf("%d", &n); n--; ){
scanf("%s", s);
if(s[]=='C'){
if(s[]=='r'){
sscanf(s, "CreateProcess(%d,%d,%d)", &pid, &mem, &pro);
create_process(pid, mem, pro);
}
else if(s[]=='l'){
if(s[]=='M')
close_max_memory();
else{
sscanf(s, "CloseProcess(%d)", &pid);
close_process(pid);
}
}
else{
sscanf(s, "ChangePriority(%d,%d)", &pid, &pro);
change_priority(pid, pro);
}
}
else if(s[]=='A'){
sscanf(s, "AddMessage(%d,%d)", &pid, &pro);
add_message(pid, pro);
}
else if(s[]=='G'){
sscanf(s, "GetMemory(%d,%d)", &pid, &mem);
modify_memory(pid, mem);
}
else if(s[]=='F'){
sscanf(s, "FreeMemory(%d,%d)", &pid, &mem);
modify_memory(pid, -mem);
}
else{
if(s[]){
sscanf(s, "RunProcess(%d)", &pid);
run_process(pid);
}
else run();
}
}
return ;
}