UVa 540

Team Queue.cpp

#include <iostream>
#include <map>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

vector<int> TeamQueue;
map<int, int> TeamIDMappingTable;
map<int, int> TailOfTeam;

void updateAllTailOfTeamFrom(int teamID, int offset)
{
	auto indexOfTeamQueue = TailOfTeam[teamID];
	for (auto &mappingItem: TailOfTeam)
	{
		if (mappingItem.second >= indexOfTeamQueue)
		{
			mappingItem.second += offset;
		}
	}
}

void removeNotExistItem()
{
	auto index = TailOfTeam.begin();
	while (index != TailOfTeam.end())
	{
		if (index->second == -1)
		{
			index = TailOfTeam.erase(index);
		}
		else
		{
			index++;
		}
	}
}

void init()
{
	TeamQueue.clear();
	TeamIDMappingTable.clear();
	TailOfTeam.clear();
}

void createNewTeam(int teamID)
{
	auto teamLength = 0, elementID = 0;
	scanf("%d", &teamLength);
	for (auto i = 0; i < teamLength; i++)
	{
		scanf("%d", &elementID);
		TeamIDMappingTable[elementID] = teamID;
	}
}

void enqueue(int elementID)
{
	auto teamID = TeamIDMappingTable[elementID];
	if (TailOfTeam.count(teamID))
	{
		TeamQueue.insert(TeamQueue.begin() + TailOfTeam[teamID] + 1, elementID);
		updateAllTailOfTeamFrom(teamID, 1);
	}
	else
	{
		TeamQueue.push_back(elementID);
		TailOfTeam[teamID] = TeamQueue.size() - 1;
	}
}

int dequeue()
{
	auto elementID = TeamQueue[0];
	auto teamID = TeamIDMappingTable[elementID];
	TeamQueue.erase(TeamQueue.begin());
	updateAllTailOfTeamFrom(teamID, -1);
	removeNotExistItem();
	return elementID;
}

int main()
{
	auto t = 0, k = 1;
	while (~scanf("%d", &t))
	{
		if (t == 0)
		{
			break;
		}

		init();
		printf("Scenario #%d\n", k++);
		for (auto i = 0; i < t; i++)
		{
			createNewTeam(i);
		}

		auto command = string {};
		while (cin >> command)
		{
			if (command[0] == 'S')
			{
				break;
			}
			else if (command[0] == 'E')
			{
				auto elementID = 0;
				cin >> elementID;
				enqueue(elementID);
			}
			else if (command[0] == 'D')
			{
				printf("%d\n", dequeue());
			}
		}

		puts("");
	}
	return 0;
}