Cod sursa(job #864734)

Utilizator dariusdariusMarian Darius dariusdarius Data 25 ianuarie 2013 18:17:40
Problema Congr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct Mystruct {int nr,i;} v[600005];
class MyComp
{
public:inline bool operator()(Mystruct a, Mystruct b)
    {
        return a.nr<b.nr;
    }
};
int l[600005];
int main()
{
    freopen("congr.in","r",stdin);
    freopen("congr.out","w",stdout);
    int i,j,p,n,st,dr,k,s;
    scanf("%d",&p);
    n=p*2-1;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&v[i].nr);
        v[i].i=i;
    }
    sort(v+1,v+n+1,MyComp());
    for(i=1;i<=n;i++) v[i].nr%=p;
    st=1,dr=0;
    while(st<=p)
        if(dr-st+1==p)
        {
            l[++k]=s;
            s=(s-v[st++].nr+v[++dr].nr+p)%p;
        }
        else
            s=(s+v[++dr].nr)%p;
    for(i=1;i<=p;i++)
    {
        if(l[i]==0)
        {
            for(j=i;j<=p+i-1;j++)
                printf("%d ",v[j].i);
            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=(s-v[st++].nr+v[++dr].nr+p)%p;
            }
            else
                s=(s+v[++dr].nr)%p;
        for(i=1;i<=p;i++)
            if(l[i]==0)
            {
                for(j=i;j<=p+i-1;j++)
                    printf("%d ",v[j].i);
                return 0;
            }
    }
    return 0;
}