10145 - Lock Manager

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

10145 - Lock Manager

Post by Ivan Golubev » Wed Jul 24, 2002 11:36 am

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

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Thu Jul 25, 2002 5:06 am

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.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Jul 25, 2002 11:46 am

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!

mirage
New poster
Posts: 11
Joined: Sat Jan 19, 2008 9:37 pm

Lock manager

Post by mirage » Tue Feb 26, 2008 2:30 pm

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????

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 10145 - Lock Manager

Post by dibery » Sat Jan 24, 2015 10:28 am

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
Life shouldn't be null.

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: Lock manager

Post by dibery » Sat Jan 24, 2015 10:32 am

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.
Life shouldn't be null.

hrkns
New poster
Posts: 2
Joined: Sun Jan 25, 2015 3:30 pm

Re: 10145 - Lock Manager

Post by hrkns » Sun Jan 25, 2015 3:34 pm

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!
learning english...

dibery
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 10145 - Lock Manager

Post by dibery » Wed Jan 28, 2015 4:27 pm

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
Life shouldn't be null.

alecassis
New poster
Posts: 10
Joined: Sat Sep 20, 2014 6:36 am

Re: 10145 - Lock Manager

Post by alecassis » Thu Jan 29, 2015 4:47 am

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;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10145 - Lock Manager

Post by brianfry713 » Fri Jan 30, 2015 1:57 am

Input:

Code: Select all

1

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

Code: Select all

GRANTED
GRANTED
DENIED
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”