OJ Board

Code: Select all

1

10 1 1 1 1 1 1
a = 4
print a
lock
b = 9
print b
unlock
print b
end
a = 3
print a
lock
b = 8
print b 
unlock
print b
end
b = 5
a = 17
print a
print b
lock
b = 21
print b
unlock
print b
end
lock
z=26
y=25
x=24
print x
printy
printz
unlock
end
k=7
lock
k=9
k=10
printk
printk
unlock
end
k=7
lock
k=9
k=10
printk
printk
unlock
end
end
k=7
lock
k=9
k=10
printk
printk
unlock
end
k=7
lock
k=9
k=10
printk
printk
unlock
end
k=7
lock
k=9
k=10
printk
printk
unlock
end

Code: Select all

1: 3
2: 3
3: 17
3: 5
4: 24
4: 25
4: 26
5: 10
5: 10
6: 10
6: 10
8: 10
8: 10
9: 10
9: 10
10: 10
10: 10
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21

Code: Select all

[code]#include <iostream>
#include <queue>

using namespace std;

struct Statement{
	char type;
	char LHS,RHS;

};

struct Program{
	char ip;
	char len;
	Statement stmt[25];
};

int stmtcost[5];
int quantum;
Program progs[10];
int progcount;
queue<int> Ques[2];
char variables[26];

int executeStmt(Statement st,int prognum,int & lockStatus){
	switch(st.type){
		case 0:
			variables[st.LHS]=st.RHS;
		break;

		case 1:
			cout<<prognum+1<<": "<<(int)variables[st.LHS]<<endl;
		break;

		case 2:
			if(lockStatus)return 1;
			lockStatus=1;
		break;

		case 3:
			lockStatus=0;
		break;

	}
	return 0;
}

void simulateEnv(){
	int nextQ=0;
	int prognum;
	int quantumT;
	int placeinBlk;
	int lockStatus=0,tempLoc;

	for(nextQ=0;nextQ<progcount;nextQ++)
		Ques[0].push(nextQ);

	nextQ=0;
	while(!Ques[0].empty()||!Ques[1].empty()){
		if(Ques[nextQ].empty()){
			nextQ^=1;
			continue;
		}
		prognum=Ques[nextQ].front();
		Ques[nextQ].pop();

		quantumT=quantum;
		tempLoc=lockStatus;

		while(quantumT>0){
			if(progs[prognum].ip>=progs[prognum].len)break;
			

			if((placeinBlk=executeStmt(progs[prognum].stmt[progs[prognum].ip],prognum,lockStatus))==1)
				break;

			quantumT-=stmtcost[progs[prognum].stmt[progs[prognum].ip].type];
			progs[prognum].ip++;

		}
		if(tempLoc==1&&lockStatus==0)
			nextQ=1;
		else
			nextQ=0;

		if(progs[prognum].ip>=progs[prognum].len)
			continue;
		else if(placeinBlk)
			Ques[1].push(prognum);
		else
			Ques[0].push(prognum);
	}
}

///////////////////
int getType(char * inputStmt, Statement & st){
	
	if(inputStmt[2]=='='){
		st.type=0;
		st.LHS=inputStmt[0]-'a';
		st.RHS=0;
		inputStmt+=4;
		while(*inputStmt)
			st.RHS=st.RHS*10+(*inputStmt++-'0');
	}
	else if(inputStmt[0]=='p'){
		st.type=1;
		st.LHS=inputStmt[6]-'a';
	}
	else if(inputStmt[0]=='l'){
		st.type=2;
	}
	else if(inputStmt[0]=='u'){
		st.type=3;
	}
	else if(inputStmt[0]=='e')
		st.type=4;
	return st.type;
}

/////////////////////


int main(){

	int casecount=0;
	int prognum,stmtnum;
	char inputStmt[10];
	
	cin>>casecount;


	while(casecount){
		cin>>progcount;
		for(prognum=0;prognum<5;prognum++)
			cin>>stmtcost[prognum];
		for(prognum=0;prognum<26;prognum++)
			variables[prognum]=0;

		cin>>quantum;
		cin.ignore(5,'\n');
		for(prognum=0;prognum<progcount;prognum++){
			stmtnum=0;
			while(1){
				cin.getline(inputStmt,9);
				if(getType(inputStmt,progs[prognum].stmt[stmtnum])==4){
					progs[prognum].len=stmtnum;
					progs[prognum].ip=0;
					break;
				}
				stmtnum++;
			}
		}
		simulateEnv();
		casecount--;
		if(casecount)
		cout<<endl;
	}
	return 0;
}

Code: Select all

/*
Author: Hao Hu (Ikki)
Problem: Concurrency Simulator
Source: 1991 acm/icpc World Finals Problem C
Date: Jan 25, 2007
*/

#include<stdio.h>
#include<string.h>

char tmp[100];
int var[26],t[5],np,tq;
int num[15],q[15],to[15];
char prog[15][30][100];
int Ready[20000],h_r,t_r;
int Blocked[20000],h_b,t_b,idx;
bool locked;

void run()
{
	idx=Ready[h_r];
	for(int i=to[idx];i<num[idx];i++)
	{
		if(prog[idx][i][0]=='e'&&prog[idx][i][1]=='n')
		{
			q[idx]-=t[4];
			return;
		}
		if(prog[idx][i][1]=='=')
		{
			char ch; int xx;
			sscanf(prog[idx][i],"%c=%d",&ch,&xx);
			var[ch-'a']=xx;
			q[idx]-=t[0];
		}
		if(prog[idx][i][0]=='p'&&prog[idx][i][1]=='r')
		{
			printf("%d: %d\n",idx+1,var[prog[idx][i][5]-'a']);
			q[idx]-=t[1];
		}
		if(prog[idx][i][0]=='l'&&prog[idx][i][1]=='o')
		{
			if(locked)
			{
				Blocked[t_b++]=idx;
				q[idx]=tq;
				to[idx]=i;
				return;
			}
			else
			{
				locked=true;
				q[idx]-=t[2];
			}
		}
		if(prog[idx][i][0]=='u'&&prog[idx][i][1]=='n')
		{
			Ready[h_r]=Blocked[h_b];
			h_r--;
			h_b++;
			q[idx]-=t[3];
			locked=false;
		}
		if(q[idx]<=0)
		{
			Ready[t_r++]=idx;
			q[idx]=tq;
			to[idx]=i+1;
			return;
		}
	}
}

int main()
{
//	freopen("new_in.txt","r",stdin);
	int test,no=0;
	scanf("%d",&test);
	getchar();
	while(test--)
	{
		if(no!=0) printf("\n");
		no++;
		memset(num,0,sizeof(num));
		memset(var,0,sizeof(var));
		gets(tmp);
		scanf("%d%d%d%d%d%d%d",&np,&t[0],&t[1],&t[2],&t[3],&t[4],&tq);
		locked=false;
		h_r=t_r=h_b=t_b=10000;
		for(int i=0;i<np;i++)
		{
			q[i]=tq;
			while(1)
			{
				gets(tmp);
				int len=0,sz=strlen(tmp);
				for(int j=0;j<sz;j++)
					if(tmp[j]!=' ')
						prog[i][num[i]][len++]=tmp[j];
				prog[i][num[i]][len]='\0';
				num[i]++;
				if(prog[i][num[i]-1][0]=='e'&&prog[i][num[i]-1][1]=='n')
					break;
			}
		}
		for(int i=0;i<np;i++)
		{
			to[i]=0;
			Ready[t_r++]=i;
		}
		while(h_r!=t_r)
		{
			run();
			h_r++;
		}
	}
	return 0;
}

Code: Select all

1

3 1 1 1 1 1 3
a = 5
print a
end
b = 7
lock
print a
print b
unlock
c = 10
print a
end
print a
print b
lock
print c
unlock
end

-------------------output-------------
1: 5
2: 5
3: 5
3: 7
2: 7
3: 10
2: 5

Code: Select all

#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<deque>
#include<queue>
#include<iostream>
#include<sstream>
using namespace std;
//vector<program> a;
map<string,int> dict;
vector<queue<string> > lines;
vector<int> is_finished;
   int case_id,program_id;
   int t1,t2,t3,t4,t5,t;
void simulate_program();

int main(){
   //read the case number
   cin>>case_id;
   string line;
   while(case_id--){
       lines.clear();
       is_finished.clear();
        //ignore blank line
        //read time info for the case
        cin>>program_id>>t1>>t2>>t3>>t4>>t5>>t;
        //getline(cin,line);
        cin.ignore(256,'\n');
        while(program_id--){
                is_finished.push_back(0);
                queue<string> program;
                getline(cin,line);
               while(line!="end"){
                    program.push(line);
                    getline(cin,line);
                }
                program.push(line);
                lines.push_back(program);
        }
//        for(vector<queue<string> >::iterator it=lines.begin();it!=lines.end();it++){
//            while(!it->empty()){
//                cout<<it->front()<<endl;
//                it->pop();
//            }
//        }
        simulate_program();
        if(case_id>1){
            putchar('\n');
        }

   }
   return 0;
}
void simulate_program(){
    int is_locked=0,index;
    deque<int> primary_queue;
    queue<int> block_queue;
    for(unsigned int i=0;i<lines.size();i++){
        primary_queue.push_back(i);
    }
    while(!primary_queue.empty()){
            index=primary_queue.front();
            primary_queue.pop_front();
            int slice=0;
            while(slice<t){
                string l=lines[index].front();
                stringstream istr(l);
                string p1,p2;
                int p3;
                istr>>p1>>p2;
                if(p1=="print"){
                        cout<<index+1<<": "<<dict[p2]<<endl;
                        slice+=t2;
                }
                else if(p1=="lock"){
                        slice+=t3;
                        if(is_locked){
                            block_queue.push(index);
                            is_finished[index]=1;
                            break;
                        }
                        else{
                            is_locked=1;
                        }
                }
                else if(p1=="unlock"){
                    slice+=t4;
                    is_locked=0;
                    if(!block_queue.empty()){
                        int i=block_queue.front();
                        block_queue.pop();
                        primary_queue.push_front(i);
                        is_finished[i]=0;
                    }
                }
                else if(p1=="end"){
                    is_finished[index]=1;
                    break;
                }
                else{
                    slice+=t1;
                    istr>>p3;
                    dict[p1]=p3;
                }
                lines[index].pop();

            }
              if(!is_finished[index]){
                    primary_queue.push_back(index);
                }
    }
    return;
}