Cod sursa(job #467371)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 28 iunie 2010 15:43:02
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

#define file_in "congr.in"
#define file_out "congr.out"

#define nmax 301000

int p,n,nr,first;
int a[2*nmax+10];
int v[2*nmax+10];
int frecv[2*nmax+10];

void citire()
{
    int i,x;
    freopen(file_in,"r",stdin);
    freopen(file_out,"w",stdout);

    scanf("%d", &p);
    for (i=1;i<=2*p-1;++i)
    {
        scanf("%d", &x);
        a[i]=x%p;
        v[i]=x;
    }

}

void solve()
{
    int i,j,suma,k,r,s;

    sort(a+1,a+2*p-1+1);

    //for(i=1;i<=2*p-1;++i)
    // printf("%d ", a[i]);
    i=p+1;
    j=2;
    while(j<=p && i<=2*p-1)
    {
        suma=a[i]-a[j];
        if (suma==0)
        {
           s=0;
            for (k=j;k<=i;++k) s+=v[k];
            //printf("A intrat la suma%d\n", suma);
            if (s%p==0)
            {
            for (k=j;k<=i;++k)
                 printf("%d ", k);
            exit(0);
            }
        }
        i++;
        j++;
    }


    suma=0;
    for (i=1;i<=p;++i)
        suma+=a[i];
        //printf("%d\n ",suma%p);
    if (suma%p==0)
    {
        for (i=1;i<=p;++i)
             printf("%d ", i);
          exit(0);
    }

    r=suma%p;
    i=p+1;
    j=2;
    //printf("%d\n", r);
    while(j<=p && i<=2*p-1)
    {
        suma=a[i]-a[j];
        if (suma==p-r)
        {
            //printf("A intrat la suma%d %d %d\n", suma,i,j);
            for (k=j;k<=i;++k)
                 frecv[k]=1;
            for (k=1;k<=p;++k)
                if (frecv[k]==1)
                frecv[k]=0;
                else
                frecv[k]=1;
                s=0;
            for (k=1;k<=2*p-1;++k)
                 if (frecv[k]) s+=v[k];
                 int ok=0;
            for (k=1;k<=2*p-1 && !ok;++k)
                 if (frecv[k]==0)
                 if ((s+v[k])%p==0)
                 {
                     frecv[k]=1;
                     ok=1;
                 }
                 if (ok)
                 {

                for (k=1;k<=2*p-1;++k)
                 if (frecv[k]) printf("%d ", k);
                 }

            exit(0);
        }
        i++;
        j++;
    }



}

int main()
{
    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}