http://acm.pku.edu.cn/JudgeOnline/problem?id=1030
Код:
#include <cstdio> #include <iostream> #include <cstring> #include <cstdlib> #include <memory> #include <algorithm> #define MAXN 100 #define MAXL 1000 using namespace std; pair<pair<int,int>,int> ans[MAXN+1]; int r[2][MAXN+1],minr[2][MAXN+1],maxr[2][MAXN+1],valid[2][MAXN+1],pos[2][MAXN+1]; char line[MAXL+1],*ptr; int c[MAXN+1]; void getrank(int r[]) { int i,k,m,n,team; gets(line); sscanf(line,"%d",&n); k=0; for(i=0;i<n;i++) { m=0; gets(line); ptr=strtok(line," \n"); while(ptr!=NULL) { team=atoi(ptr)-1; r[team]=k; c[team]++; m++; ptr=strtok(NULL," \n"); } k=k+m; } } void check(int team,int r[],int valid[],int nr) { int k; k=r[team]; if(valid[k]==-2) { return; } if(valid[k]==-1) { valid[k]=nr; } else if(valid[k]!=nr) { valid[k]=-2; } } int main() { int i,j,k,m,n,p,q,t,r0,r1,nr,prev; memset(valid,-1,sizeof(valid)); memset(pos,-1,sizeof(pos)); memset(r,-1,sizeof(r)); getrank(r[0]); gets(line); getrank(r[1]); n=0; for(i=0;i<MAXN;i++) { if(c[i]==2) { ans[n++]=make_pair(make_pair(r[0][i]+r[1][i],0),i); } } sort(ans,ans+n); m=prev=-1; for(i=0;i<n;i++) { r0=r[0][ans[i].second]; r1=r[1][ans[i].second]; if(prev!=ans[i].first.first) { m++; minr[0][m]=maxr[0][m]=r0; minr[1][m]=maxr[1][m]=r1; prev=ans[i].first.first; } else { minr[0][m]=min(minr[0][m],r0); maxr[0][m]=max(maxr[0][m],r0); minr[1][m]=min(minr[1][m],r1); maxr[1][m]=max(maxr[1][m],r1); } nr=(m<<1)+1; ans[i].first.first=nr; check(ans[i].second,r[0],valid[0],nr); check(ans[i].second,r[1],valid[1],nr); } for(j=0;j<2;j++) { for(i=1;i<=m;i++) { maxr[j][i]=max(maxr[j][i],maxr[j][i-1]); } for(i=m-1;i>=0;i--) { minr[j][i]=min(minr[j][i],minr[j][i+1]); } if(m>=0) { for(i=0;i<minr[j][0];i++) { pos[j][i]=0; } for(i=maxr[j][m]+1;i<MAXN;i++) { pos[j][i]=(m+1)<<1; } } else { for(i=0;i<MAXN;i++) { pos[j][i]=0; } } for(k=0;k<m;k++) { for(i=maxr[j][k]+1;i<minr[j][k+1];i++) { pos[j][i]=(k+1)<<1; } } } for(i=0;i<MAXN;i++) { if(c[i]==1) { if(r[0][i]>=0) { k=0; } else { k=1; } p=r[k][i]; if(valid[k][p]>=0) { ans[n++]=make_pair(make_pair(valid[k][p],0),i); } else if(pos[k][p]>=0) { ans[n++]=make_pair(make_pair(pos[k][p],p),i); } } } sort(ans,ans+n); m=0; for(i=0;i<n;i++) { if((i>0)&&(ans[i].first!=ans[i-1].first)) { printf("\n"); m=0; } if(m==0) { printf("%d",ans[i].second+1); } else { printf(" %d",ans[i].second+1); } m++; } printf("\n"); return 0; }