10145 - Lock Manager

[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

[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.

[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!

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

[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

[dibery]

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.

[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!

[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

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

[brianfry713]

Input:

Code: Select all

1

S 1 1
S 2 1
X 1 1
#

AC output:

Code: Select all

GRANTED
GRANTED
DENIED