Cod sursa(job #984103)

Utilizator andrettiAndretti Naiden andretti Data 13 august 2013 15:36:26
Problema Semne Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.21 kb
#include<stdio.h>
#include<algorithm>
#include<ctime>
#include<stdlib.h>
#include<bitset>
#define maxn 50005
using namespace std;

int n,np,nm;
int a[maxn];
int p[maxn],m[maxn];
long long s,sum;
bitset <maxn> sol;

void read()
{
    scanf("%d%lld",&n,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sol[i]=rand()%2;
        if(sol[i]) p[++np]=i,sum+=a[i];
        else m[++nm]=i,sum-=a[i];
    }
}

void solve()
{
    int ind;
    while(sum!=s)
    {
        if(sum>s)
        {
            ind=rand()%np+1;
            sum-=2*a[p[ind]];
            sol[p[ind]]=0;
            m[++nm]=p[ind];
            swap(p[ind],p[np--]);
        }

        if(sum<s)
        {
            ind=rand()%nm+1;
            sum+=2*a[m[ind]];
            sol[m[ind]]=1;
            p[++np]=m[ind];
            swap(m[ind],m[nm--]);
        }
    }
}

void print()
{
    for(int i=1;i<=n;i++)
     if(sol[i])
      printf("+");
      else printf("-");
}

int main()
{
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);

    srand(time(0));
    read();
    solve();
    print();

    fclose(stdin);
    fclose(stdout);
    return 0;
}