Отримання знань

дистанційна підтримка освіти школярів


Оценка
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;
}
 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)