Untitled
plain_text
a month ago
2.8 kB
3
Indexable
Never
#include <unordered_map> #include <string> #include <set> #include <iostream> #define MAXN 40005 using namespace std; struct Node{ int begin, size; bool empty; Node *prev, *next; void init(int begin, int size, bool empty){ this->begin=begin; this->size=size; this->empty=empty; }; } pool[MAXN]; int idx; Node* getNode(){ return &pool[idx++]; } void connect(Node *a, Node *b){ a->next=b; b->prev=a; } struct Linklist{ Node *head, *tail; Linklist(){ head=new Node(); tail=new Node(); } void init(){ connect(head,tail); } void add(Node *ref, Node *n){ Node *temp=ref->next; connect(ref, n); connect(n, temp); } void del(Node *a){ connect(a->prev, a->next); } } ll; struct Comparator{ bool operator()(Node *n1, Node *n2){ if(n1->size != n2->size) return n1->size > n2->size; return n1->begin < n2->begin; } }; unordered_map<int, Node*> hashRoom; set<Node*, Comparator> setRoom; int emptyRoom; int n; void init(int N) { n=N; idx=0; hashRoom.clear(); setRoom.clear(); ll.init(); Node *a=getNode(); a->init(1, N, true); setRoom.insert(a); ll.add(ll.head, a); emptyRoom=N; return; } int arrive(int mId){ emptyRoom--; auto it=setRoom.begin(); Node* cur=*it; ll.del(cur); setRoom.erase(cur); Node *prev=cur->prev; Node *next=cur->next; int begin=cur->begin; int end=begin+ cur->size-1; if(begin==1){ Node* curA=getNode(); curA->init(1, 1, false); cur->init(2, cur->size-1, true); ll.add(prev, curA); ll.add(curA, cur); setRoom.insert(cur); hashRoom[mId]=curA; return 1; } else if(end==n){ cur->init(cur->begin,cur->size-1,true); Node *curB= getNode(); curB->init(n,1, false); ll.add(prev, cur); ll.add(cur, curB); setRoom.insert(cur); hashRoom[mId]=curB; return n; } int select=(begin+end)/2; cur->init(select, 1, false); hashRoom[mId]=cur; ll.add(prev, cur); if(select-begin>0){ Node* leftCur=getNode(); leftCur->init(begin, select-begin, true); setRoom.insert(leftCur); ll.add(prev, leftCur); } if(end-select>0){ Node *rightCur=getNode(); rightCur->init(select+1,end-select, true); setRoom.insert(rightCur); ll.add(cur, rightCur); } return select; } int leave(int mId){ emptyRoom++; Node *cur=hashRoom[mId]; Node *prev=cur->prev; Node *next=cur->next; hashRoom.erase(mId); ll.del(cur); cur->empty=true; if(prev->empty==true){ cur->begin=prev->begin; cur->size+=prev->size; setRoom.erase(prev); ll.del(prev); prev=prev->prev; } if(next->empty==true){ cur->size+=next->size; setRoom.erase(next); ll.del(next); } ll.add(prev, cur); setRoom.insert(cur); return emptyRoom; }