Cod sursa(job #731177)

Utilizator mihai995mihai995 mihai995 Data 7 aprilie 2012 17:22:24
Problema Semne Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

const long long N=50005;
long long v[N],a[N],b[N],n,S;
char semn[N];

ifstream in("semne.in");
ofstream out("semne.out");

inline void change(char &a)
{
    if (a=='+')
        a='-';
    else
        a='+';
}

void edit(long long a[],long long b[])
{
    int p=rand()%a[0]+1;
    S+=2*v[a[p]];
    v[a[p]]*=-1;
    b[++b[0]]=p;
    change(semn[a[p]]);
    a[p]=a[a[0]--];

}

int main()
{
    in>>n>>S;
    srand(time(NULL));
    for (int i=1;i<=n;i++)
    {
        in>>v[i];
        S-=v[i];
        a[++a[0]]=i;
        semn[i]='+';
    }
    while (S)
        if (S>0)
            edit(b,a);
        else
            edit(a,b);
    out<<semn+1<<"\n";
    return 0;
}