#include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma warning(disable:4996) typedef long long ll; #define MIN(a, b) ((a)>(b)? (b): (a)) #define MAX(a, b) ((a)<(b)? (b): (a)) #define LINF 9223300000000000000 #define INF 2140000000 const long long MOD = 1000000007; //const long long MOD = 998244353; using namespace std; int n; // seatの数 int Q; // 人の数 vector a,b; // input vector vv; // vv[i]:i番目の優先順位番号の席のID(0<=i vv2; // vvの逆変換 set > > z; // time,flag(1:add, 0:del),id set s0; // ptが0の席の優先順位番号 set s1; // ptが1,2の席の優先順位番号 vector pt; // pt[i]:優先順位番号iの席のpoint:その席に座っている人がいたら+10、隣りに座っている人がいたら+1 vector status; // 各人が座った席の優先順位番号(>=0) -1なら待機中 set ss; // 待機中の人のid void update(int q, int q_pt) // 優先順位番号qの席のポイントがq_ptになったときのs0,s1の更新 { if(q_pt==0) s0.insert(q); else s0.erase(q); if(q_pt==1 || q_pt==2) s1.insert(q); else s1.erase(q); } void seat(int id, int q, ll tt) // idの人が優先順位番号qの席に時刻ttに座る { status[id]=q; pt[q]+=10; update(q,pt[q]); if(vv[q]>0) { int tmp=vv2[vv[q]-1]; pt[tmp]++; update(tmp,pt[tmp]); } if(vv[q]0) { int tmp=vv2[vv[q]-1]; pt[tmp]--; update(tmp,pt[tmp]); } if(vv[q]=0 && tmp=0 && tmpfirst; int flag=it0->second.first; int id=it0->second.second; z.erase(*it0); if(tt_prev!=tt || flag_prev!=flag) { if(!ss.empty() && !s0.empty()) { int id=(*ss.begin()); ss.erase(id); int q=(*s0.begin()); s0.erase(q); seat(id,q,tt_prev); continue; } if(!ss.empty() && !s1.empty()) { int id=(*ss.begin()); ss.erase(id); int q=(*s1.begin()); s1.erase(q); seat(id,q,tt_prev); continue; } } if(flag==1) { if(!s0.empty()) { int q=(*s0.begin()); seat(id,q,tt); } else if(!s1.empty()) { int q=(*s1.begin()); seat(id,q,tt); } else { status[id]=-1; ss.insert(id); } } else { assert(status[id]>=0); int q=status[id]; unseat(id,q); } if(z.empty()) { while(!ss.empty() && !s0.empty()) { int id=(*ss.begin()); ss.erase(id); int q=(*s0.begin()); s0.erase(q); seat(id,q,tt); } while(!ss.empty() && !s1.empty()) { int id=(*ss.begin()); ss.erase(id); int q=(*s1.begin()); s1.erase(q); seat(id,q,tt); } } tt_prev=tt; flag_prev=flag; } for(i=0; i=0); printf("%d\n", vv[status[i]]+1); } return 0; }