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