[C++] 純文本查看 復制代碼
#include<iostream>
#include<map>
#include<queue>
#include<algorithm>
#define endl '\n'
using namespace std;
int n,m;
struct school{
map<int,int> s2r; //student to rank, rank=-1:正取, 0:落榜, >0:備取順序
priority_queue<pair<int,int>> stu; //錄取學生 first:rank second:stu id
int count; //正取上限人數
}sch[60];
struct student{
vector<int> gn; //志願順序
int real; //錄取第幾志願
}stu[100100];
void procstu(int si) //把學生填入志願 si:student id
{
student &s=stu[si];
int goal=s.real+1;
while(goal<s.gn.size())
{
school &gch=sch[s.gn[goal]];
int mrank=gch.s2r[si];
if( mrank!=0 && (gch.stu.size() < gch.count || mrank < gch.stu.top().first) )
{
gch.stu.push(make_pair(mrank,si));
s.real=goal;
if(gch.stu.size()>gch.count)
{
stu[gch.stu.top().second].real=-1;
int tmp=gch.stu.top().second;
gch.stu.pop();
procstu(tmp);
}
return;
}
goal++;
}
s.real=-1;
}
int main()
{
ios::sync_with_stdio(0);
//cin.tie(0);
int T;
cin>>T;
while(T--)
{
//input
cin>>n>>m;
fill_n(sch,m+5,school());
fill_n(stu,n+10,student());
for(int i=1;i<=n;i++)
{
int t;
cin>>t;
stu.gn.resize(t);
for(int j=0;j<t;j++)
cin>>stu.gn[j];
stu.real=-1;
}
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
sch.count=a;
for(int j=0;j<b;j++)
{
int t;
cin>>t;
if(j<a)
sch.s2r[t]=-1;
else
sch.s2r[t]=j-a+1;
}
}
//solve
for(int i=1;i<=n;i++)
procstu(i);
//output
for(int i=1;i<=n;i++)
{
int t=stu.real;
if(t==-1)cout<<-1<<endl;
else cout<<stu.gn[t]<<endl;
}
}
}