> //超时了的AVL
> #include <cstdio>
> using namespace std;
> int Abs(int a){return a<0?-a:a;}
> struct Tnode{
> 	int key,data,d2,sz;
> 	char b;
> 	Tnode *lc,*rc;
> 	Tnode(){lc=rc=NULL;b=0;data=d2=2100000000;}
> 	Tnode **c(int a){return a==-1?&lc:&rc;}
> 	~Tnode(){if (lc)delete lc;if (rc)delete rc;}
> };
> #define ROTATE(y,x,d) (*(y->c(d)))=(*(x->c(-d)));(*(x->c(-d)))=y;
> struct AVL{
> 	Tnode root;
> 	int H;
> 	AVL(){root.rc=NULL;H=0;}
> 	void tIns(int k){
> 		Tnode *t,*s,*p,*q,*r;
> 		int a;
> 		if (!root.rc){root.rc=new Tnode;root.rc->key=k;H=1;return;}
> 		t=&root;s=p=root.rc;
> 		while (1){
> 			if (k<p->key){
> 				q=p->lc;
> 				if (!q){q=new Tnode;p->lc=q;break;}
> 				if (q->b){t=p;s=q;}
> 				p=q;
> 			}else if (k>p->key){
> 				q=p->rc;
> 				if (!q){q=new Tnode;p->rc=q;break;}
> 				if (q->b){t=p;s=q;}
> 				p=q;
> 			}else return;
> 		}
> 		q->key=k;p=root.rc;
> 		while (p!=q){
> 			if (k<p->key){p->sz++;p=p->lc;}
> 			else p=p->rc;
> 		}
> 		a=((k<s->key)?-1:1);r=p=(*(s->c(a)));
> 		while (p!=q){
> 			if (k<p->key){p->b=-1;p=p->lc;}
> 			else {p->b=1;p=p->rc;}
> 		}
> 		if (s->b==0){s->b=a;H++;return;}
> 		else if (s->b==-a){s->b=0;return;}
> 		else{
> 			if (r->b==a){
> 				ROTATE(s,r,a);
> 				s->b=r->b=0;p=r;
> 				if (a==1)r->sz+=s->sz;
> 				else if (a==-1)s->sz-=r->sz;
> 			}else{
> 				p=(*(r->c(-a)));
> 				ROTATE(r,p,-a);ROTATE(s,p,a);
> 				if (p->b==a){s->b=-a;r->b=0;}
> 				else if (p->b==0)s->b=r->b=0;
> 				else {s->b=0;r->b=a;}
> 				p->b=0;
> 				if (a==1){r->sz-=p->sz;p->sz+=s->sz;}
> 				else if (a==-1){p->sz+=r->sz;s->sz-=p->sz;}
> 			}
> 			if (s==t->rc)t->rc=p;else t->lc=p;
> 		}
> 	}
> 	Tnode* Find(int k){Tnode *p;p=root.rc;
> 		while (p && p->key!=k)if (k<p->key)p=p->lc;else p=p->rc;
> 		return p;
> 	}
> 	Tnode* Find_index(int id){Tnode *p;p=root.rc;
> 		while (p && p->sz!=id+1)if (id>=p->sz){id-=p->sz;p=p->rc;}else p=p->lc;
> 		return p;
> 	}
> };
> int main(){
> 	AVL blocked,used;
> 	char cmd[10];
> 	Tnode *p;
> 	int tr,it;
> 	while (scanf("%s",cmd)!=EOF && cmd[0]!='#'){
> 		scanf("%d %d",&tr,&it);
> 		p=blocked.Find(tr);
> 		if (p)puts("IGNORED");
> 		else{
> 			p=used.Find(it);
> 			if (p && ((Abs(p->data)!=tr && (cmd[0]=='X' || p->data<0))
> 				|| (p->d2!=2100000000 && Abs(p->d2)!=tr && (cmd[0]=='X' || p->d2<0)))){
> 				puts("DENIED");
> 				blocked.tIns(tr);
> 			}else{
> 				puts("GRANTED");
> 				used.tIns(it);
> 				p=used.Find(it);
> 				if (p->data==2100000000){
> 					if (cmd[0]=='X')p->data=-tr;
> 					else p->data=tr;
> 				}else{
> 					p->d2=p->data;
> 					if (cmd[0]=='X')p->data=-tr;
> 					else p->data=tr;
> 				}
> 			}
> 		}
> 	}
> 	return 0;
> }
> 
> //过了的Hash
> #include <cstdio>
> #include <string.h>
> using namespace std;
> int Abs(int a){return a<0?-a:a;}
> struct Lnode{
> 	int key,data,d2;
> 	Lnode *next;
> 	Lnode(){next=NULL;data=d2=2100000000;}
> };
> #define MODULO 9101
> struct HashTable{
> 	Lnode *head[MODULO];
> 	HashTable(){memset(head,0,sizeof(head));}
> 	Lnode *tIns(int k){
> 		int w;
> 		Lnode *p;
> 		w=k%MODULO;
> 		p=head[w];
> 		while (p){
> 			if (p->key==k)return p;
> 			p=p->next;
> 		}
> 		p=new Lnode;
> 		p->key=k;
> 		p->next=head[w];
> 		head[w]=p;
> 		return p;
> 	}
> 	Lnode *Find(int k){
> 		int w;
> 		Lnode *p;
> 		w=k%MODULO;
> 		p=head[w];
> 		while (p){
> 			if (p->key==k)return p;
> 			p=p->next;
> 		}
> 		return NULL;
> 	}
> };
> int main(){
> 	HashTable blocked,used;
> 	char cmd[10];
> 	Lnode *p;
> 	int tr,it;
> 	while (scanf("%s",cmd)!=EOF && cmd[0]!='#'){
> 		scanf("%d %d",&tr,&it);
> 		p=blocked.Find(tr);
> 		if (p)puts("IGNORED");
> 		else{
> 			p=used.Find(it);
> 			if (p && ((Abs(p->data)!=tr && (cmd[0]=='X' || p->data<0))
> 				|| (p->d2!=2100000000 && Abs(p->d2)!=tr && (cmd[0]=='X' || p->d2<0)))){
> 				puts("DENIED");
> 				blocked.tIns(tr);
> 			}else{
> 				puts("GRANTED");
> 				p=used.tIns(it);
> 				if (p->data==2100000000){
> 					if (cmd[0]=='X')p->data=-tr;
> 					else p->data=tr;
> 				}else{
> 					p->d2=p->data;
> 					if (cmd[0]=='X')p->data=-tr;
> 					else p->data=tr;
> 				}
> 			}
> 		}
> 	}
> 	return 0;
> }
> 

• 不是效率问题，是编译问题。最后两个算法都用110msAC了 (0) fanhqme 2009-05-30 09:35:00
  • 其实涉及到数据结构运算的时间都是几个ms就完了的 (10) AllwaysLoser 2009-05-30 11:26:26