Page 1 of 1

10145 - Lock Manager

Posted: Wed Jul 24, 2002 11:36 am
by Ivan Golubev
Are there any tricks in this problem? Is this I/O correct?

Input:
1

S 1 1
S 1 1
X 1 1
X 5 1
X 5 2
S 3 2
S 5 3
S 4 2
S 6 3
X 4 2
S 7 2
S 6 2
X 6 2
X 1 3
X 7 4
X 4 4
S 8 3
S 5 3
S 6 3
X 8 3
S 8 5
#

Output:
GRANTED
GRANTED
GRANTED
DENIED
IGNORED
GRANTED
IGNORED
GRANTED
GRANTED
DENIED
GRANTED
GRANTED
DENIED
DENIED
GRANTED
IGNORED
GRANTED
IGNORED
IGNORED
DENIED
IGNORED

Posted: Thu Jul 25, 2002 5:06 am
by wyvmak
i got the sample output with you.

what about:
1

S 1 1
S 1 1
X 1 1
X 1 1
S 1 1

the judge does seem to have tricky/good input/output

PS. the problem is multiple input, just a reminder, though i don't think it's likely to be the cause, as experienced as you are.

Posted: Thu Jul 25, 2002 11:46 am
by Ivan Golubev
Yeah, no problem with multiple input that was a problem with my attention -- I'm just used at one place 'transaction id' instead of 'item id'. The weird thing that after this it normally processed many I/Os. Silly mistake...

Fixed & accepted, thanks for the reply!

Lock manager

Posted: Tue Feb 26, 2008 2:30 pm
by mirage
hey friends,
i have a query...
the question says that the previous locks are not changed in any way
so do we have to consider only the most recently executed lock on a data item while looking for conflicts or do we have to look out for all the past locks on that data item????

Re: 10145 - Lock Manager

Posted: Sat Jan 24, 2015 10:28 am
by dibery
A test case.

Input:

Code: Select all

1

X 1 1
X 2 1
S 2 2
S 1 1
Output:

Code: Select all

GRANTED
DENIED
IGNORED
GRANTED

Re: Lock manager

Posted: Sat Jan 24, 2015 10:32 am
by dibery
mirage wrote:hey friends,
i have a query...
the question says that the previous locks are not changed in any way
so do we have to consider only the most recently executed lock on a data item while looking for conflicts or do we have to look out for all the past locks on that data item????
You have to check all past locks.
Once the allocation of a lock is made, this lock is never released (until the end of this case).
New locks may come in afterwards, if permitted.
The input is not too tricky.

Re: 10145 - Lock Manager

Posted: Sun Jan 25, 2015 3:34 pm
by hrkns
can somebody helps? i don't know why i'm getting WA, this is the code

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<iomanip>
#include<utility>
#include<set>

using namespace std;

typedef struct
{
	char mode;
	set<string> trids;
}thing;

typedef unsigned long long uent;
typedef pair<string, thing> pair_;

int main()
{
	uent n;
	cin >> n;
	while(n--)
	{
		char c;
		string trid, item;
		map<string, thing > db;
		map<string, thing >::iterator it;
		vector<string> ignored;
		do
		{
			cin >> c;
			if(c != '#')
			{
				cin >> trid >> item;
				if(find(ignored.begin(), ignored.end(), trid) != ignored.end())
					cout << "IGNORED" << endl;
				else
				{
					it = db.find(item);
					if(it == db.end())
					{
						cout << "GRANTED" << endl;
						thing aux;
						aux.mode = c;
						aux.trids.insert(trid);
						db.insert(pair_(item, aux));
					}
					else
					{
						if(it->second.mode == 'S')
						{
							if(c == 'S')
							{
								cout << "GRANTED" << endl;
								it->second.trids.insert(trid);
							}
							else
							{
								if(it->second.trids.size() == 1 && it->second.trids.find(trid)!=it->second.trids.end())
								{
									cout << "GRANTED" << endl;
									it->second.mode = c;
								}
								else
								{
									cout << "DENIED" << endl;
									ignored.push_back(trid);
								}
							}
						}
						else
						{
							if(it->second.trids.find(trid)!=it->second.trids.end())
							{
								cout << "GRANTED" << endl;
								it->second.mode = c;
							}
							else
							{
								cout << "DENIED" << endl;
								ignored.push_back(trid);
							}
						}
					}
				}
			}
		}while(c != '#');
		if(n)cout << endl;
	}
	return 0;
}
thanks!

Re: 10145 - Lock Manager

Posted: Wed Jan 28, 2015 4:27 pm
by dibery
Input:

Code: Select all

1

X 1 1
X 2 1
S 2 2
S 1 1
S 2 1
X 2 1
X 2 2
S 3 1
#
Output:

Code: Select all

GRANTED
DENIED
IGNORED
GRANTED
IGNORED
IGNORED
IGNORED
DENIED

Re: 10145 - Lock Manager

Posted: Thu Jan 29, 2015 4:47 am
by alecassis
Can anybody help me? I don't know why I'm getting WA.

Code: Select all

#include <cstdio>
#include <map>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef pair<int, int> ii;

#define EXCLUSIVE -1
#define SHARED -10
#define BLOCKED 0

int main () {
	char line [110];
	map<int, ii> items;
	map<int, int> transactions;
	int t, id_transaction, id_item;
	char type;
	scanf("%d\n\n", &t);
	for (int num_case = 0; num_case < t; num_case++) {
		if (num_case) printf("\n");
		items.clear();
		transactions.clear();
		while (cin >> type && type != '#') {
			scanf("%d %d", &id_transaction, &id_item);
			if (transactions.count(id_transaction)) {
				if (transactions	[id_transaction] == BLOCKED) {
					printf("IGNORED\n");
				}
			}
			else if (items.count(id_item)) {
				if (items[id_item].second != id_transaction && (type == 'X' || items[id_item].first == EXCLUSIVE)) {
					printf("DENIED\n");
					transactions[id_transaction] = BLOCKED;
				}
				else {
					if (type == 'X')
						items[id_item].first = EXCLUSIVE;
					printf("GRANTED\n");
				}
			}
			else {
				if (type == 'X') {
					items[id_item] = ii(EXCLUSIVE, id_transaction);
				}
				else {
					items[id_item] = ii(SHARED, id_transaction);
				}
				printf("GRANTED\n");
			}
		}
	}
	return 0;
}

Re: 10145 - Lock Manager

Posted: Fri Jan 30, 2015 1:57 am
by brianfry713
Input:

Code: Select all

1

S 1 1
S 2 1
X 1 1
#
AC output:

Code: Select all

GRANTED
GRANTED
DENIED