Cod sursa(job #466617)

Utilizator MKLOLDragos Ristache MKLOL Data 27 iunie 2010 12:09:11
Problema Congr Scor 100
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 1.91 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<stdlib.h>
#include<time.h>

struct cel{
int nr,i;
} v[303030*2];
bool cmp(cel a, cel b)
{
    return a.nr<b.nr;
}
int P,N,st,dr,l[303030*2],k,S,A;
using namespace std;
int main()
{
    freopen("congr.in","r",stdin);
    freopen("congr.out","w",stdout);

    scanf("%d",&P);

    N=P*2-1;

    for(int i=1;i<=N;++i)
        {
        scanf("%d",&v[i].nr);
        v[i].i=i;
        }

    sort(v+1,v+N+1,cmp);

    for(int i=1;i<=N;++i)
       v[i].nr=v[i].nr%P;

        st=1,dr=0;
        while(st<=P)
        {
            if(dr-st+1==P)
            {
                l[++k]=S;
                S-=v[st].nr;
                ++st;
                S+=v[++dr].nr;
                if(S<0)
                S+=P;
                S%=P;

            }
            else
            {
                S+=v[++dr].nr;
                S%=P;
            }

        }
        for(int i=1;i<=P;++i)
        {

        if(l[i]==0)
        {
       for(int j=i;j<=P+i-1;++j)
            printf("%d ",v[j].i);
          i=N+1;
        }
        if(i==N+1)
            return 0;
        }
        while(1)
        {
        random_shuffle(v+1,v+N+1);
         st=1,dr=0,k=0,S=0;
        while(st<=P)
        {
            if(dr-st+1==P)
            {
                l[++k]=S;
                S-=v[st].nr;
                ++st;
                S+=v[++dr].nr;
                if(S<0)
                S+=P;
                S%=P;

            }
            else
            {
                S+=v[++dr].nr;
                S%=P;
            }

        }
        for(int i=1;i<=P;++i)
        {

        if(l[i]==0)
        {
       for(int j=i;j<=P+i-1;++j)
       {
        printf("%d ",v[j].i);
       }

          i=N+1;

        }
        if(i==N+1)
            return 0;
        }

        }
}