首页 > 代码库 > 【模拟】【set】hdu 4789 ICPC Ranking
【模拟】【set】hdu 4789 ICPC Ranking
写了一晚上,TLE到死,我选择GG
喵的好像还是前几年我校出的题,这整场都……tm……
改日在战
/*TLE代码*/
#include<cstdio> #include<vector> #include<string> #include<cstring> #include<map> #include<algorithm> #include<iostream> #include<set> int e; using namespace std; map<string,int>ma; struct data{ vector<int>lasts; int solved,penalty; string name;/* data(const int &_solved,const int &_penalty,const vector<int> & _lasts,const string &_name){ solved=_solved; penalty=_penalty; lasts=_lasts; name=_name; }*/ data(const string &_name){ solved=penalty=0; name=_name; lasts.clear(); } data(){} }; bool operator < (const data &a,const data &b){ if(a.solved!=b.solved){ return a.solved>b.solved; } if(a.penalty!=b.penalty){ return a.penalty<b.penalty; } for(int i=a.lasts.size()-1,j=b.lasts.size()-1;i>=0 && j>=0;--i,--j){ if(a.lasts[i]!=b.lasts[j]){ return a.lasts[i]<b.lasts[j]; } } return a.name>b.name; } typedef set<data>::iterator set_ITER; struct Query{ string name; char pro; int t,type; }Q[50010]; bool operator < (const Query &a,const Query &b){ if(a.t!=b.t){ return a.t<b.t; } return a.type<b.type; } set<data>S; data A[50010],output[50010]; int p; int B[50010][26]/*,D[50010][26]*/,aftersubs[50010][26]; int C[50010][26],E[50010][26]; int n,m,T,t,ZU; int main(){ // freopen("i.in","r",stdin); char tmp1[10],tmp2[10]; scanf("%d",&ZU); for(int zu=1;zu<=ZU;++zu){ printf("Case #%d:\n",zu); // memset(aftersubs,0,sizeof(int)*(e+1)*26); // memset(B,0,sizeof(int)*(e+1)*26); // memset(C,0,sizeof(int)*(e+1)*26); // memset(D,0,sizeof(int)*(e+1)*26); // memset(E,0,sizeof(int)*(e+1)*26); ma.clear(); e=0; S.clear(); p=0; S.insert(data("")); scanf("%d%d%d%d",&n,&m,&T,&t); for(int i=1;i<=n;++i){ cin>>Q[i].name; if(!ma[Q[i].name]){ ma[Q[i].name]=++e; A[e]=data(Q[i].name); S.insert(A[e]); } scanf("%s%d%s",tmp1,&Q[i].t,tmp2); Q[i].pro=tmp1[0]; if(tmp2[0]==‘E‘){ Q[i].type=0; } if(tmp2[0]==‘N‘){ Q[i].type=1; } else{ Q[i].type=2; } } sort(Q+1,Q+n+1); for(int i=1;i<=n;++i){ int id=ma[Q[i].name]; if(Q[i].t>=t){ ++aftersubs[id][Q[i].pro-‘A‘]; continue; } if(Q[i].type==0 || (Q[i].type==2 && C[id][Q[i].pro-‘A‘])){ continue; } if(Q[i].type==1){ ++B[id][Q[i].pro-‘A‘]; // ++D[id][Q[i].pro-‘A‘]; } else{ S.erase(A[id]); C[id][Q[i].pro-‘A‘]=Q[i].t; E[id][Q[i].pro-‘A‘]=Q[i].t; ++A[id].solved; A[id].penalty+=(Q[i].t+B[id][Q[i].pro-‘A‘]*20); A[id].lasts.push_back(Q[i].t); S.insert(A[id]); } } int rank=1; set_ITER jt=S.begin(); ++jt; for(set_ITER it=S.begin();;++it,++rank,++jt){ if(jt==S.end()){ break; } cout<<(*it).name<<‘ ‘<<rank<<‘ ‘<<(*it).solved<<‘ ‘<<(*it).penalty; int id=ma[(*it).name]; for(int i=0;i<m;++i){ putchar(‘ ‘); if(C[id][i]){ putchar(‘+‘); if(B[id][i]){ printf("%d",B[id][i]); } } else{ if(aftersubs[id][i]){ if(B[id][i]){ printf("-%d",B[id][i]); } else{ putchar(‘0‘); } putchar(‘/‘); printf("%d",aftersubs[id][i]); } else{ if(B[id][i]){ printf("-%d",B[id][i]); } else{ putchar(‘.‘); } } } } puts(""); } int From; for(int i=1;i<=n;++i){ if(Q[i].t>=t){ From=i; break; } } for(int i=From;i<=n;++i){ int id=ma[Q[i].name]; if(Q[i].type==0 || (Q[i].type==2 && C[id][Q[i].pro-‘A‘])){ continue; } else if(Q[i].type==1){ ++B[id][Q[i].pro-‘A‘]; } else{ C[id][Q[i].pro-‘A‘]=Q[i].t; ++A[id].solved; } } set_ITER it=S.end(); --it; --it; while(1){ bool allsolved=0; while((*it).solved==A[ma[(*it).name]].solved){ if(it==S.begin()){ allsolved=1; break; } jt=it; --jt; output[++p]=(*it); S.erase(it); it=jt; } if(allsolved){ output[++p]=(*S.begin()); break; } data nextFrom; if(it!=S.begin()){ --it; nextFrom=(*it); ++it; } int id=ma[(*it).name]; for(int i=0;i<m;++i){ if(C[id][i]!=E[id][i]){ E[id][i]=C[id][i]; data tmp=(*it); set_ITER jt=it; data __next=*(++jt); ++tmp.solved; tmp.penalty+=(C[id][i]+B[id][i]*20); tmp.lasts.push_back(C[id][i]); S.erase(it); S.insert(tmp); it=S.find(tmp); ++it; if((*it).name!=__next.name){ cout<<tmp.name<<‘ ‘<<(*it).name<<‘ ‘<<tmp.solved<<‘ ‘<<tmp.penalty<<endl; it=S.find(nextFrom); } else{ --it; } break; } } } for(int i=p,rank=1;i>=1;--i,++rank){ int id=ma[output[i].name]; cout<<output[i].name<<‘ ‘<<rank<<‘ ‘<<output[i].solved<<‘ ‘<<output[i].penalty; for(int j=0;j<m;++j){ putchar(‘ ‘); if(C[id][j]){ putchar(‘+‘); if(B[id][j]){ printf("%d",B[id][j]); } } else{ if(B[id][j]){ printf("-%d",B[id][j]); } else{ putchar(‘.‘); } } } puts(""); } for(int i=1;i<=n;++i){ int id=ma[Q[i].name]; aftersubs[id][Q[i].pro-‘A‘]= B[id][Q[i].pro-‘A‘]= C[id][Q[i].pro-‘A‘]= E[id][Q[i].pro-‘A‘]=0; } } return 0; }
【模拟】【set】hdu 4789 ICPC Ranking
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。