Cod sursa(job #466709)

Utilizator DraStiKDragos Oprica DraStiK Data 27 iunie 2010 13:32:11
Problema Congr Scor 40
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 2.01 kb
#include <algorithm>
#include <stdio.h>
#include <time.h>
using namespace std;

#define BRUTE_LIMIT 2000
#define DIM 300005
#define sc second
#define fs first

pair <int,int> v[DIM<<1];
double start;
int p,n,nrp;
int s[DIM];

void read ()
{
    int i;

    scanf ("%d",&p);
    for (i=1; i<(p<<1); ++i)
    {
        scanf ("%d",&v[i].fs);
        v[i].sc=i;
    }
}

void solve_brute ()
{
    int i,j,k,ok;

    n=(p<<1)-1;
    sort (v+1,v+n+1);
    do
    {
        ok=0;
        for (i=1; i<=n; ++i)
        {
            s[i]=(s[i-1]+v[i].fs)%p;
            if (!s[i] && i<=p-nrp)
            {
                nrp+=i;
                for (j=1; j<=i; ++j)
                    printf ("%d ",v[j].sc);
                for (j=i+1; j<=n; ++j)
                    v[j-i]=v[j];
                n-=i;
                ok=1;
            }
        }
        for (i=1; i<n && !ok; ++i)
            for (j=i+1; j<=n && !ok; ++j)
                if (s[j]==s[i] && !ok && j-i<=p-nrp)
                {
                    nrp+=j-i;
                    for (k=i+1; k<=j; ++k)
                        printf ("%d ",v[k].sc);
                    for (k=j+1; k<=n; ++k)
                        v[i+k-j]=v[k];
                    n-=j-i;
                    ok=1;
                }
    }
    while (nrp<p);
}

void solve_bulan ()
{
    int i,sum;

    while ((clock()-start)/CLOCKS_PER_SEC<0.75)
    {
        sum=0;
        random_shuffle (v+1,v+(p<<1));
        for (i=1; i<=p; ++i)
            sum+=v[i].fs;
        if (!(sum%p))
        {
            for (i=1; i<=p; ++i)
                printf ("%d ",v[i].sc);
            return ;
        }
    }
    random_shuffle (v+1,v+(p<<1));
    for (i=1; i<=p; ++i)
        printf ("%d ",v[i].sc);
}

int main ()
{
    start=clock ();
    freopen ("congr.in","r",stdin);
    freopen ("congr.out","w",stdout);

    read ();
    if (p<=BRUTE_LIMIT)
        solve_brute ();
    else
        solve_bulan ();

    return 0;
}