Cod sursa(job #466732)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 27 iunie 2010 13:51:20
Problema Congr Scor 70
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.99 kb
#include<stdio.h>

int p,viz[300006],v[300006],s,f[300006];
int u,vec[300006],st,dr;

int main ()
{
    int i,j,cam,cviz;
    freopen("congr.in","r",stdin);
    freopen("congr.out","w",stdout);
    scanf("%d",&p);
    for(i=1;i<=2*p-1;i++)
    {
        scanf("%d",&v[i]);
        v[i]%=p;
        viz[v[i]]++;
        if(viz[v[i]]==p)
        {
            for(j=1;j<=i;j++)
                if(v[i]==v[j])
                    printf("%d ",i);
            printf("\n");
            return 0;
        }
    }
    for(i=1;i<=p;i++)
    {
        s+=v[i];
        s%=p;
    }
    if(!s)
    {
        for(i=1;i<=p;i++)
            printf("%d ",i);
        printf("\n");
        return 0;
    }
    for(i=p+1;i<=2*p-1;i++)
        f[v[i]]=i;
    for(i=1;i<=p;i++)
    {
        cam=(p-s+v[i])%p;
        if(f[cam])
        {
            for(j=1;j<i;j++)
                printf("%d ",j);
            for(j=i+1;j<=p;j++)
                printf("%d ",j);
            printf("%d\n",f[cam]);
            return 0;
        }
    }
    u=0;
    for(i=0;i<p;i++)
    {
        cviz=viz[i];
        while(viz[i])
        {
            vec[++u]=i;
            viz[i]--;
        }
        viz[i]=cviz;
    }
    s=0;
    for(i=1;i<=p;i++)
    {
        s+=vec[i];
        s%=p;
    }
    st=1;dr=p;
    for(i=p+1;i<2*p && s;i++)
    {
        s+=v[i];
        s-=v[i-p];
        s%=p;
    }
    if(!s)
    {
        for(i=1;i<2*p;i++)
            if(v[i]==vec[st] && viz[v[i]])
            {
                printf("%d ",i);
                st++;
                viz[v[i]]--;
            }
            else
                if(v[i]==vec[dr] && viz[v[i]])
                {
                    printf("%d ",i);
                    dr--;
                    viz[v[i]]--;
                }
                else
                    if(v[i]>st && v[i]<dr && viz[v[i]])
                    {
                        printf("%d ",i);
                        viz[v[i]]--;
                    }
         printf("\n");
         return 0;
    }

    return 0;
}