Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

不能忍了！此题Hash能过AVL却要超时。帮忙看看！

Posted by fanhqme at 2009-05-29 17:39:16 on Problem 1749

//超时了的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;
}

Followed by:

UP (4) fanhqme 2009-05-29 18:47:18
UP (6) fanhqme 2009-05-29 20:58:06
原来是编译器对define语句处理的策略不同！ (103) fanhqme 2009-05-29 21:38:37
多么希望得到一个测评用的编译器，好在提交之前就发现问题（而不是在A+B上用2小时提交27来排除法测试） (15) fanhqme 2009-05-29 21:42:33
- 准确的说是33分钟制造13个ac，7个tle，7个ole。fanhqme被折磨得时间感都没有了 (19) AllwaysLoser 2009-05-29 21:46:32
  - 或许也只有时间的堆砌与血的经验才能发现并避免类似事情。但愿竞赛用的测评系统不要太灵异 (26) fanhqme 2009-05-29 21:49:31
    - 写竞赛的时候谁不是连memset都不敢用了？尽量把代码写的工整才是王道. (31) AllwaysLoser 2009-05-29 21:50:41
      - 但是如果写的太工程了，一个avl模版（见下）怎么可能在73行内写完？ (1900) fanhqme 2009-05-29 21:52:34
        至少多写点括号是有备无患的 (65) AllwaysLoser 2009-05-29 21:54:49
Re:这有什么，hash效率比AVL当然一般来说会要高很多。 (4280) Arithmetic 2009-05-30 07:07:48
- 不是效率问题，是编译问题。最后两个算法都用110msAC了 (0) fanhqme 2009-05-30 09:35:00
  - 其实涉及到数据结构运算的时间都是几个ms就完了的 (10) AllwaysLoser 2009-05-30 11:26:26

Post your reply here:

User ID:
Password:
Title:

Content:

> //超时了的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;
> }
>

Home Page Go Back To top