ZeroJudge E564: Team Queue

UVa 00540 – Team Queue

"Queues" and "Priority Queues" are well-known data structures for most people.
However, even though "Team Queue" occurs frequently in daily life, it is not as widely known.
In a "Team Queue," each element belongs to a team. When an element enters the queue, it first searches the queue from head to tail to check if its teammates (elements from the same team) are already in the queue.
If they are, they will be placed after the last member of the team. If not, it will be placed at the end of the queue.
Dequeueing works the same as in a regular queue: elements are processed from head to tail in the order they appear in the team queue.
Your task is to write a program to simulate a Team Queue.

Sample Inputs/Outputs

Thought Process

To implement Team Queue, you can declare a map to store the team of each member. Team Queue can be implemented using a two-dimensional array.

You need to declare a map to store the current position of each team in the two-dimensional array. When performing ENQUEUE and the value of the team in the map is 0, you should push back a new one-dimensional array containing strings into the two-dimensional array. Then, set the value of the team in the map to the size of the two-dimensional array, which is the last position.

When performing DEQUEUE, output and delete the element at [0][0] of the two-dimensional array. After deletion, check if the first one-dimensional array still has data. If it doesn't, delete this one-dimensional array. Then, update all the data in the map. You can use a for loop like for(auto it:Map) to update the data. If it.second == 1, it means this is the one-dimensional array that was just deleted, so set its value to 0. If it's neither 1 nor 0, decrease the value in the map by 1.

Sample Code－ZeroJudge E564: Team Queue

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int T, count = 1;
    while (cin >> T && T != 0) {
        map<string, int>MAP;
        for (int i = 0; i<T; i++) {
            int N;
            cin >> N;
            for (int j = 0; j<N; j++) {
                string str;
                cin >> str;
                MAP[str] = i;
            }
        }
        string str;
        vector<vector<string>>v;
        map<int, int>hi;
        cout << "Scenario #" << count << "\n";
        count++;
        while (cin >> str && str != "STOP") {
            if (str == "ENQUEUE") {
                string s;
                cin >> s;
                int index = hi[MAP[s]];
                if (index == 0) {
                    vector<string>tmp;
                    tmp.push_back(s);
                    v.push_back(tmp);
                    hi[MAP[s]] = v.size();
                }
                else v[index-1].push_back(s);
                continue;
            }
            cout << v[0][0] << "\n";
            v[0].erase(v[0].begin());
            if (v[0].empty()) {
                v.erase(v.begin());
                for (auto it:hi) {
                    if (it.second == 1) hi[it.first] = 0;
                    else if (it.second != 0) hi[it.first]--;
                }
            }
        }
        cout << "\n";
    }
}

//ZeroJudge E564
//Dr. SeanXD