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"); } }