Problem C: ChongQueue

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 52 Solved: 22
[Submit][Status][Web Board]

Description

I solemnly introduce to you a new kind of species ---- bugs (of course not worms on your earth). I am a member of the population. We live in the Chongplanet, which is a well-developed planet. Sometimes my friends and I play with you programmer, but you often can't find us where, so foolish. Oh, I have not told you my name,you can called me ChongChong.
There are many interesting things on Chongplanet. Although Chongplanet was developed vary well, some places still need to queue. How can it be same with queue on earth? Thinking of queue at my school, we have a lot of students each class. when I want to enqueue, I'll find whether there are my classmates in the queue or not. If yes, I can insert behind my classmates (you human are not allowed to jump the queue, so foolish); If not, then I can only stand behind the whole queue.
Even allowed to jump the queue, Bugs also complained about queuing. I thought of a solution. Simulate the queue with a program, so that Bugs do not need stand in the queue. This is your task. We Bugs are clever, so it's foolish people's task to write such a low-level program.

Input

The input file will contain one or more test cases. Each test case begins with the number of classes t ( 1 <= t <= 1000). Then t classes descriptions follow, each one consisting of the number of students belonging to the class and the students themselves. A class may consist of up to 1000 students. Students are string, the length of which is in the range [1, 10).

Finally, a list of commands follows. A test case may contain up to 100000 commands. There are three different kinds of commands:

ENQUEUE x - enter student x into the queue
DEQUEUE - process the first student and remove it from the queue
STOP - end of test case

The input will be terminated by a value of 0 for t.

Output

For each test case, first print a line saying ``Scenario #k", where k is the number of the test case. Then, for each DEQUEUE command, print the student which is dequeued on a single line. Print a blank line after each test case, even after the last one.

Sample Input

3 a b c

3 d e f

ENQUEUE a

ENQUEUE d

ENQUEUE b

ENQUEUE e

ENQUEUE c

ENQUEUE f

DEQUEUE

STOP

5 qqqqqq wwwwww eeeeee rrrrrr tttttt

6 aaaaaa ssssss dddddd ffffff gggggg hhhhhh

ENQUEUE qqqqqq

ENQUEUE aaaaaa

ENQUEUE wwwwww

ENQUEUE eeeeee

ENQUEUE rrrrrr

ENQUEUE tttttt

DEQUEUE

ENQUEUE ssssss

ENQUEUE dddddd

DEQUEUE

STOP

Sample Output

Scenario #1

Scenario #2

qqqqqq

wwwwww

eeeeee

rrrrrr

tttttt

aaaaaa

HINT

分析:

1.用map快速求解ENQUEUE的人的班级号与班级内序号；

2.用二叉树表示排队关系，一个孩子连接到下一个班，另一个孩子连接到班级内的下一名同学；

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <map>
using namespace std;

typedef struct My
{
    bool f=true;
    int c,x;
    struct My *nx=NULL;
    struct My *nc=NULL;
} My;
My *One;
char a[1000][1000][10];
char buf[10];

map<string,int>cc;
map<string,int>xx;

void push(char s[10])
{
    if (One==NULL)
    {
        One=new My;
        One->c=cc[s];
        One->x=xx[s];
    }
    else
    {
        int c=cc[s];
        int x=xx[s];
        My *t=One;
        while (t->c!=c&&t->nc!=NULL)
        {
            t=t->nc;
        }
        if (t->c!=c)
        {
            t->nc=new My;
            t=t->nc;
            t->c=c;
            t->x=x;
        }
        else
        {
            while (t->nx!=NULL)t=t->nx;
            t->nx=new My;
            t=t->nx;
            t->c=c;
            t->x=x;
        }
    }
}

void pop(bool s)
{
    My *t;
    if (s)puts(a[One->c][One->x]);
    if (One->nx!=NULL)
    {
        t=One->nx;
        t->nc=One->nc;
        delete One;
        One=t;
    }
    else
    {
        t=One->nc;
        delete One;
        One=t;
    }
}


int main(void)
{
    int it=0;
    int n;
    while (scanf("%d",&n),n>0)
    {
        cc.clear();
        xx.clear();
        printf("Scenario #%d
",++it);
        while (One!=NULL)pop(0);
        for (int i=0; i<n; i++)
        {
            int m;
            scanf("%d",&m);
            for (int j=0; j<m; j++)
            {
                scanf("%s",a[i][j]);
                cc[a[i][j]]=i;
                xx[a[i][j]]=j;
            }
        }


        gets(buf);
        while (scanf("%s",buf),buf[0]!='S')
        {
            if (buf[0]=='E')
            {
                scanf("%s",buf);
                push(buf);
            }
            else
            {
                pop(1);
            }
        }
        puts("");
    }
    return 0;
}

View Code