Cod sursa(job #1233313)

Utilizator touristGennady Korotkevich tourist Data 25 septembrie 2014 09:19:01
Problema Semne Scor 25
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.39 kb
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <queue>
#define Nmax 50005

using namespace std;

queue <int> Minus,Plus;
int a[Nmax],sol[Nmax],v[Nmax];

int main()
{
    int N,i,r,x,aux;
    long long S,suma=0;
    srand(time(0));
    freopen ("semne.in","r",stdin);
    freopen ("semne.out","w",stdout);
    scanf("%d%lld", &N,&S);
    for(i=1;i<=N;++i)
    {
        scanf("%d", &a[i]);
        v[i]=i;
    }
    for(i=1;i<=1000;++i)
    {
        r=rand()%N+1; x=rand()%N+1;
        aux=v[r]; v[r]=v[x]; v[x]=aux;
    }
    for(i=N;i;--i)
    {
        r=rand()%2;
        if(!r)
        {
            suma+=a[v[i]];
            Plus.push(i);
        }
        else
        {
            suma-=a[v[i]];
            Minus.push(i);
        }
    }
    while(suma!=S)
    {
        if(suma<S)
        {
            x=Minus.front(); Minus.pop();
            suma=suma+2*a[v[x]]; Plus.push(x);
        }
        else
        {
            x=Plus.front(); Plus.pop();
            suma=suma-2*a[v[x]]; Minus.push(x);
        }
    }
    while(!Minus.empty())
    {
        x=Minus.front(); Minus.pop();
        sol[v[x]]=0;
    }
    while(!Plus.empty())
    {
        x=Plus.front(); Plus.pop();
        sol[v[x]]=1;
    }
    for(i=1;i<=N;++i)
        if(!sol[i]) printf("-");
        else printf("+");
    printf("\n");
    return 0;
}