Problem H. 选拔赛
Time limit: 6 seconds
Memory limit: 256 megabytes
郑州大学 ACM 实验室选拔赛开始了！
本次选拔赛采取个人赛的形式，一共有 k 名实验室成员报名参与。你作为本次选拔赛的现场工作人员，需要为每一个参赛成员安排一个合适的位置。已知选拔赛场地一共有 n×m 个位置，每个位置都可以看做 n 行 m 列的网格图中的一个网格。为了保证公平性，你将所有的参赛成员按照姓名升序排序，并按照排好的顺序以先行后列的优先级将所有参赛成员分配到位置上（如果场地的位置一共有三行三列，则第一个成员被安排到第一行第一列，第二个成员被安排到第一行第二列，第三个成员被安排到第一行第三列，第四个成员被安排到第二行第一列，以此类推）。保证座位的数量大于等于报名成员的数量。
然而，在选拔赛当天，有一些同学因故申请缺席，同时也有另一些同学虽然没有报名，但也希望参与选拔赛。作为现场工作人员，你当然要尽可能地满足这些同学的所有需求。同学们需求的具体格式描述如下：
absent name 表示姓名为 name 的同学申请缺席，你需要将原先分配给该名同学的座位标记为空闲，并输出位置所在的行和列（中间用空格隔开）。保证此时姓名为 name 的同学一定被分配了位置。
signup name 表示姓名为 name 的同学申请参加选拔赛，你需要按照先行后列的优先级将该名同学分配到第一个空闲的位置上，并输出位置所在的行和列（中间用空格隔开）；如果所有位置皆已满员，则输出 fail，即使此后有位置空出，也不会再重新考虑此次申请。保证此时姓名为 name 的同学一定没有被分配座位。（可以反复申请缺席再申请参赛）
name 被描述为两个由空格间隔开的字符串，如 tong su，第一个字符串代表名，第二个字符串代表姓。按照姓名升序排序即先以姓的字典序为第一关键字升序排序，对于姓相同的同学，再按照名的字典序为第二关键字升序排序。为了简化问题，保证所有同学的姓与名均仅由小写字母组成，且长度均小于等于
10 个字符，且不存在两个同学同名同姓。
在所有需求结束后，你需要输出这 n × m 个位置的情况，具体格式见输出要求。
Input
输入第一行包含三个整数 n, m, k(1 ≤ n, m ≤ 500, 0 ≤ k ≤ n × m)，含义如上所示。
接下来 k 行，其中第 i 行两个字符串 ai, bi(|ai|, |bi| ≤ 10) 表示开始时第 i 个参赛报名成员的名和姓。
接下来一行，包含一个整数 q(1 ≤ q ≤ 2 × 105)，表示同学们需求的数量（需求发生的先后顺序即读入的先后顺序）。
接下来 q 行，每行两个字符串描述需求，具体的格式如上所示。
Output
对于每个需求，都应输出一行表示对需求的反馈，具体格式如上所示。
在所有需求结束后，你需要输出一个 n × m 的矩阵表示所有位置的情况：
若 (i, j) 位置为空，则在第 i 行第 j 列输出 −1；
若 (i, j) 位置不为空，且该位置的同学是在处理需求前便分配好的，则在第 i 行第 j 列输出 0；
若 (i, j) 位置不为空，且该位置的同学是在处理第 x 个需求（从 1 开始标号）时分配的，则在第 i 行第 j 列输出 x。
Example standard input
2 2 3
xihang yue
siwei zhang
tong su
6
absent tong su
signup yang chen
signup tong su
signup su tong
absent xihang yue
signup su tong
standard output
1 1
1 1
2 2
fail
1 2
1 2
2 6
0 3

分析题意，得我们要实现三个功能
1.维护座位和人员信息，某个座位为空或有人，某个人在哪个座位
2.维护一个堆用于储存新加入比赛的人所坐座位的优先级，先行后列
3.释放退赛的人的座位并加入2.的堆
对1，用vis[][]存储座位上的人，map<string,pair<int,int> >存储某个人的座位
对2、3，用priority_queue<pair<int,int> >q维护即可

#include<bits/stdc++.h>
using namespace std;
map<string,pair<int,int> > M;//名字 ，座位 
priority_queue<pair<int,int> >q;//有哪些空位 
string x[250010];
int vis[510][510];
/*char buf[1<<15],*fs,*ft;
inline char getc(){return (fs==ft && (ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs)) ? 0:*fs++;}
inline int read()
{
    int num=0,f=1;char ch=getc();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getc();}
    while(isdigit(ch)) {num=(num<<1)+(num<<3)+(ch^48);ch=getc();}
    return num*f;
}*/
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    memset(vis,-1,sizeof(vis));
    int n,m,k;
    cin>>n>>m>>k;
    //string nam;
    string k1,k2,k3,kn;
    for(int i=1;i<=k;++i)
    {
        cin>>k1>>k2;
        x[i]=k2+' '+k1;
        //cout<<x[i]<<endl;
    }
    sort(x+1,x+1+k);
    //for(int i=1;i<=k;++i) cout<<x[i]<<' '<<M[x[i]].first<<' '<<M[x[i]].second<<endl;

    int i=1,j=1;
    for(int o=1;o<=k;++o)
    {
        M[x[o]]=make_pair(i,j);
        vis[i][j]=0;
        ++j;
        if(j>m) j-=m,++i;
    }
    for(int o=k+1;o<=n*m;++o)
    {
        q.push(make_pair(-i,-j));
        ++j;
        if(j>m) j-=m,++i;
    }//for(int i=1;i<=k;++i) cout<<x[i]<<' '<<M[x[i]].first<<' '<<M[x[i]].second<<endl;

    int qq;cin>>qq;
    for(int i=1;i<=qq;++i)
    {
        cin>>k1>>k2>>k3;
        kn=k3+' '+k2;
        //cout<<kn<<endl;
        //cout<<k1<<k2<<k3<<endl;
        if(k1=="absent")
        {
            int aa=M[kn].first,bb=M[kn].second;
            q.push(make_pair(-aa,-bb));
            cout<<aa<<' '<<bb<<endl;
            vis[aa][bb]=-1;
            //M[kn]=make_pair(0,0);
        }
        //cout<<q.top().first<<"&"<<q.top().second;
        if(k1=="signup")
        {
            if(!q.size())
            {
                cout<<"fail"<<endl;
            }
            else
            {   
                int aa=-q.top().first,bb=-q.top().second;
                M[kn]=make_pair(aa,bb);
                cout<<aa<<' '<<bb<<endl;
                q.pop();
                vis[aa][bb]=i;
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            cout<<vis[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}
/**************************************************************
    Problem: 4569
    User: contest21_42
    Language: C++
    Result: 正确
    Time:2764 ms
    Memory:30740 kb
****************************************************************/