Cod sursa(job #478630)

Utilizator freak93Adrian Budau freak93 Data 19 august 2010 15:05:50
Problema Semne Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<fstream>
#include<cstdlib>

using namespace std;

const char iname[]="semne.in";
const char oname[]="semne.out";
const int maxn=50005;

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

int a[maxn],l[maxn],r[maxn],i,x,rez[maxn],k,n,m;
long long S,s;

int main()
{
    f>>k>>S;
    for(i=1;i<=k;++i)
    {
        f>>a[i];
        x=rand()%2;
        if(x)
            s+=a[i],l[++n]=i;
        else
            s-=a[i],r[++m]=i;
    }
    do
    {
        if(s==S)
            break;
        if(s>S)
        {
            x=rand()%n+1;
            s-=2*a[l[x]];
            r[++m]=l[x];
            l[x]=l[n--];
        }
        else
        {
            x=rand()%m+1;
            s+=2*a[r[x]];
            l[++n]=r[x];
            r[x]=r[m--];
        }
    }while(1);
    for(i=1;i<=n;++i)
        rez[l[i]]=1;
    for(i=1;i<=k;++i)
        if(rez[i])
            g<<"+";
        else
            g<<"-";
    g<<"\n";
}