Untitled

#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;
}