fork download
copy 
  1. #include<iostream>
  2. #include<map>
  3. #include<queue>
  4. #include<algorithm>
  5. #define endl '\n'
  6. using namespace std;
  7. int n,m;
  8. struct school{
  9.     map<int,int> s2r; //student to rank, rank=-1:正取, 0:落榜, >0:備取順序
  10.     priority_queue<pair<int,int>> stu; //錄取學生 first:rank second:stu id
  11.     int count;
  12. }sch[60];
  13. struct student{
  14.     vector<int> gn; //志願順序
  15.     int real; //錄取第幾志願
  16. }stu[100100];
  17. void procstu(int si)
  18. {
  19.     student &s=stu[si];
  20.     int goal=s.real+1;
  21.     while(goal<s.gn.size())
  22.     {
  23.         school &gch=sch[s.gn[goal]];
  24.         int mrank=gch.s2r[si];
  25.         if( mrank!=0 && (gch.stu.size() < gch.count || mrank < gch.stu.top().first) )
  26.         {
  27.             gch.stu.push(make_pair(mrank,si));
  28.             s.real=goal;
  29.             if(gch.stu.size()>gch.count)
  30.             {
  31.                 stu[gch.stu.top().second].real=-1;
  32.                 int tmp=gch.stu.top().second;
  33.                 gch.stu.pop();
  34.                 procstu(tmp);
  35.             }
  36.             return;
  37.         }
  38.         goal++;
  39.     }
  40.     s.real=-1;
  41. }
  42. int main()
  43. {
  44.     ios::sync_with_stdio(0);
  45.     //cin.tie(0);
  46.  
  47.     int T;
  48.     cin>>T;
  49.     while(T--)
  50.     {
  51. //        cout<<"no "<<T<<endl;
  52.         cin>>n>>m;
  53.         fill_n(sch,m+5,school());
  54.         fill_n(stu,n+10,student());
  55.         for(int i=1;i<=n;i++)
  56.         {
  57.             int t;
  58.             cin>>t;
  59.             stu[i].gn.resize(t);
  60.             for(int j=0;j<t;j++)
  61.                 cin>>stu[i].gn[j];
  62.             stu[i].real=-1;
  63.         }
  64.         for(int i=1;i<=m;i++)
  65.         {
  66.             int a,b;
  67.             cin>>a>>b;
  68.             sch[i].count=a;
  69.             for(int j=0;j<b;j++)
  70.             {
  71.                 int t;
  72.                 cin>>t;
  73.                 if(j<a)
  74.                     sch[i].s2r[t]=-1;
  75.                 else
  76.                     sch[i].s2r[t]=j-a+1;
  77.             }
  78.         }
  79.         for(int i=1;i<=n;i++)
  80.             procstu(i);
  81.         for(int i=1;i<=n;i++)
  82.         {
  83.             int t=stu[i].real;
  84.             if(t==-1)cout<<-1<<endl;
  85.             else cout<<stu[i].gn[t]<<endl;
  86.         }
  87.     }
  88. }
  89.  
Success #stdin #stdout 0s 5048KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lN7CFt
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!