Cod sursa(job #552671)

Utilizator laurionLaurentiu Ion laurion Data 12 martie 2011 18:11:15
Problema Congr Scor 100
Compilator cpp Status done
Runda steleinf2010seniori Marime 1.27 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

#define maxn 600010

long n, i, j, k, p, r, ok, x, sum;
long f[maxn], v[maxn], fol[maxn];

long getn(long tip)
{
    long x;
    x=rand()%(2*p-1)+1;
    while(fol[x]!=tip)
        x=rand()%(2*p-1)+1;
    return x;
}

int main()
{
    srand(time(0));
    freopen("congr.in", "r", stdin);
    freopen("congr.out", "w", stdout);
    scanf("%d", &p);
    for(i=1; i<2*p; i++)
    {
        scanf("%d", &v[i]);
        v[i]=v[i]%p;
        r=v[i];
        f[r]++;
        if(f[r]==p)
        {
            printf("%d ", i);
            while(--i)
                if(v[i]==r)
                    printf("%d ", i);
            printf("\n");
            return 0;
        }
    }
    for(i=1; i<p; i++)
    {
        fol[i]=1;
        f[v[i]]--;
        sum=(sum+v[i])%p;
    }
    while(f[p-sum]==0)
    {
        x=getn(0);
        fol[x]=1;
        f[v[x]]--;
        sum=(sum+v[x])%p;
        x=getn(1);
        fol[x]=0;
        f[v[x]]++;
        sum=(sum-v[x]+p)%p;
    }
    ok=0;
    for(i=1; i<2*p; i++)
    {
        if(fol[i]==1)
            printf("%d ", i);
        if(fol[i]==0 && p-sum==v[i] && (!ok))
        {
            ok=1;
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}