Cod sursa(job #466749)

Utilizator freak93Adrian Budau freak93 Data 27 iunie 2010 14:04:25
Problema Congr Scor 100
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 1 Marime 2.75 kb
#include<fstream>
#include<cstdlib>

using namespace std;

const char iname[]="congr.in";
const char oname[]="congr.out";
const int maxn=300005;

ifstream f(iname);
ofstream g(oname);

int a[maxn],s[maxn],d[maxn],i,n,p,s1,s2,step,leftv[maxn],rightv[maxn],orn,pasi;

int rez1()
{
    for(i=1;i<=n;++i)
    {
        f>>a[i];s[i]=i;a[i]%=n;
        s1+=a[i];
        if(s1>=n)
            s1-=n;
        ++leftv[a[i]];
    }
    orn=n;
    n*=2;
    --n;
    for(p=1;i<=n;++i,++p)
    {
        f>>a[i];d[p]=i;a[i]%=orn;
        s2+=a[i];
        if(s2>=orn)
            s2-=orn;
        ++rightv[a[i]];
    }
    n=(n+1)/2;

    srand(time(0));
    step=1;
    while((step==2||s1!=0)&&(step==1||s2!=0))
    {
        ++pasi;
        if(step==1)
            if(leftv[n-s2])
            {
                for(i=1;i<=n;++i)
                    if(a[s[i]]==n-s2)
                    {
                        d[n]=s[i];
                        break;
                    }
                s2=0;
                step=2;
                break;
            }
            else
            {
                p=rand()%n+1;
                d[n]=s[p];
                s[p]=s[n];
                s1-=a[d[n]];
                --leftv[a[d[n]]];
                ++rightv[a[d[n]]];
                if(s1<0)
                    s1+=n;
                s2+=a[d[n]];
                if(s2>=n)
                    s2-=n;
                step=2;
            }
        else
            if(rightv[n-s1])
            {
                for(i=1;i<=n;++i)
                    if(a[d[i]]==n-s1)
                    {
                        s[n]=d[i];
                        break;
                    }
                step=1;
                s1=0;
                break;
            }
            else
            {
                p=rand()%n+1;
                s[n]=d[p];
                d[p]=d[n];
                --rightv[a[s[n]]];
                ++leftv[a[s[n]]];
                s2-=a[s[n]];
                if(s2<0)
                    s2+=n;
                s1+=a[s[n]];
                if(s1>=n)
                    s1-=n;
                step=1;
            }
    }

    if(step==1)
        for(i=1;i<=n;++i)
            g<<s[i]<<" ";
    else
        for(i=1;i<=n;++i)
            g<<d[i]<<" ";
    g<<"\n";
}

/*int rez2()
{
    int m[605][305][305];
    m[0][0][0]=1;
    for(i=1;i<=n*2-1;++i)
    {
        f>>a[i];
        a[i]%=n;
        for(int j=1;j<n;++j)
            for(int k=1;k<=n;++k)
            {
                m[i&1][j][k]=m[i-1&1][j][k];
                if(m[i&1][j][k]==0)
                {
                    int p=k-a[i];
                    if(p<0)
                        p+=n;
                    m[i&1][j][k]=m[i-1&1][j-1][p];
                }
            }
    }*/
int main()
{
    f>>n;
    rez1();
}