Cod sursa(job #1514544)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 31 octombrie 2015 12:07:54
Problema Semne Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <bits/stdc++.h>
#define NMAX 50001

using namespace std;

ifstream in("semne.in");
ofstream out("semne.out");
int n;
long long int s,a[NMAX];
long long int x = 0;
int add[NMAX],low[NMAX];
int u = 0, p = 0;
bool a_sem[NMAX];

int main()
{
    in>>n>>s;
    for(int i=1;i<=n;i++)
        in>>a[i];
    in.close();
    //
    for(int i=1;i<=n;i++)
    {
        if(x<s)
        {
            add[++u] = i;
            x+=a[i];
        }
        else
        {
            low[++p] = i;
            x-=a[i];
        }
    }
    int b;
    while(x!=s)
    {
        if((x<s) && (p>0))
        {
            b = rand()%p+1;
            x+=2*a[low[b]];
            add[++u] = low[b];
            low[b] = low[p];
            p--;
        }
        else
            if(u>0)
        {
            b = rand()%u+1;
            x-=2*a[add[b]];
            low[++p] = add[b];
            add[b] = add[u];
            u--;
        }
    }
    for(int i=1;i<=u;i++)
        a_sem[add[i]] = 1;
    for(int i=1;i<=p;i++)
        a_sem[low[i]] = 0;
    for(int i=1;i<=n;i++)
        if(a_sem[i] == 1)
        out<<"+";
    else
        out<<"-";
    out<<'\n';
    out.close();
    return 0;
}