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;
}