PKU 2380 Sales Report
http://poj.org/problem?id=2380
50万個くらいの商品のIDとセールスポイントのIDと売れた個数が入力されるので、
商品のID*セールスポイントのID という表にして売れた個数を出力しろというような問題。
入出力が遅すぎて死にまくりました。
ハッシュ+自作入出力
typedef struct node_{ int f,s; int val; node_* next; }node; node ent[600000]; int esz; const int HashMod = 80021; node* hash[HashMod]; int maxlen; void add(int f,int s,int v){ int ha=abs(f+(s<<18))%HashMod; int tlen=0; for(node* p=hash[ha];p;p=p->next,++tlen) if(p->f==f && p->s==s){ p->val += v; return; } maxlen=max(tlen,maxlen); node* p=ent+esz++; p->f=f; p->s=s; p->val=v; p->next = hash[ha]; hash[ha]=p; } int get(int f,int s){ int ha=abs(f+(s<<18))%HashMod; for(node* p=hash[ha];p;p=p->next) if(p->f==f && p->s==s) return p->val; return 0; } int getint(){ char c; while(!isdigit(c=getchar())); int ret=c&15; while(isdigit(c=getchar())) ret=(ret<<3)+(ret<<1)+(c&15); return ret; } char out[2000000]; int cidx; int dig(int v){ int ret=0; do{ ++ret; v/=10; }while(v); return ret; } void putint(int v){ int k=dig(v)-1; do{ out[cidx+k]=v%10+'0'; v/=10; k-=2; ++cidx; }while(v); out[cidx++]=' '; out[cidx]=0; } main(){ int n(getint()); vector<int> row(n),col(n); rep(i,n){ int q=getint(); int s=getint(); int v=getint(); col[i]=q; row[i]=s; add(q,s,v); } //cerr<<"input"<<endl; sort(ALL(row)); sort(ALL(col)); row.erase(unique(ALL(row)),row.end()); col.erase(unique(ALL(col)),col.end()); //cerr<<"out start"<<endl; printf("-1 "); cidx=0; FOR(it,col) putint(*it); out[--cidx]=0; puts(out); FOR(it,row){ cidx=0; putint(*it); FOR(cit,col) putint(get(*cit,*it)); out[--cidx]=0; puts(out); } //cerr<<maxlen<<endl; }