POJ2259 Team Queue

変なことができるデータ構造を作れという問題。

コード中でpriority_queueにseとかいう名前がついてるのは定数倍改善のためにsetをpriority_queueに書き換えただけで特に深い意味はない。

#include<stdio.h>
#include "stdafx.h"
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<iostream>
using namespace std;
typedef pair<pair<int,int>,pair<int,int> >pi4;
int main()
{
	for(int p=1;;p++)
	{
		int num;
		scanf("%d",&num);
		if(num==0)
		{
			break;
		}
		printf("Scenario #%d\n",p);
		map<int,int>ma;
		for(int i=0;i<num;i++)
		{
			int zan;
			scanf("%d",&zan);
			for(int j=0;j<zan;j++)
			{
				int za;
				scanf("%d",&za);
				ma.insert(make_pair(za,i));
			}
		}
		priority_queue<pi4>se;
		int ban[1000];
		int now=0;
		int kos[1000];
		fill(ban,ban+num,-1);
		fill(kos,kos+num,0);
		int jun=0;
		for(;;)
		{
			string str;
			cin>>str;
			if(str=="STOP")
			{
				break;
			}
			if(str=="DEQUEUE")
			{
				pi4 zan=se.top();
				printf("%d\n",-zan.second.second);
				se.pop();
				kos[-zan.second.first]--;
			}
			if(str=="ENQUEUE")
			{
				int zan;
				scanf("%d",&zan);
				int mz=ma[zan];
				if(kos[mz]==0)
				{
					se.push(make_pair(make_pair(-now,-jun),make_pair(-mz,-zan)));
					jun++;
					ban[mz]=now;
					now++;
					kos[mz]++;
				}
				else
				{
					se.push(make_pair(make_pair(-ban[mz],-jun),make_pair(-mz,-zan)));
					kos[mz]++;
					jun++;
				}
			}
		}
		printf("\n");
	}
}